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 (239kB)
Free to read: http://dx.doi.org/10.1016/j.aam.2008.03.005
*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 Item Control Page

Downloads

Downloads per month over past year