Catalog Home Page

A connection between palindromic and factor complexity using return words

Bucci, M., Deluca, A., Glen, A. and Zamboni, L. (2009) A connection between palindromic and factor complexity using return words. Advances in Applied Mathematics, 42 (1). pp. 60-74.

[img] PDF - Authors' Version
Download (234kB)
    Link to Published Version: http://dx.doi.org/10.1016/j.aam.2008.03.005
    *Open access, no subscription required

    Abstract

    In this paper we prove that for any infinite word w whose set of factors is closed under reversal, the following conditions are equivalent: (I)all complete returns to palindromes are palindromes;(II)P (n) + P (n + 1) = C (n + 1) - C (n) + 2 for all n, where P (resp. C) denotes the palindromic complexity (resp. factor complexity) function of w, which counts the number of distinct palindromic factors (resp. factors) of each length in w.

    Publication Type: Journal Article
    Publisher: Academic Press
    Copyright: 2008 Elsevier Inc.
    URI: http://researchrepository.murdoch.edu.au/id/eprint/3806
    Item Control Page

    Downloads

    Downloads per month over past year