Palindrome complexity

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We study the palindrome complexity of infinite sequences on finite alphabets, i.e., the number of palindromic factors (blocks) of given length occurring in a given sequence. We survey the known results and obtain new results for some sequences, in particular for Rote sequences and for fixed points of primitive morphisms of constant length belonging to the class P substitutions of Hof-Knill-Simon. We also give an upper bound for the palindrome complexity of a sequence in terms of its (block-)complexity.
24 pages, dedicated to Jean Berstel for his 60th birthday

Keywords

Combinatorics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/61661

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0106121
 http://arxiv.org/abs/math/0106121
 Theor. Comput. Science 292 (2003) 9 - 31

Collections

arXiv