Palindromic prefixes and episturmian words

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:113

Article

Fischler, Stephane

关键词: palindrome;    prefix;    Sturmian word;    episturmian word;    Fibonacci word;   

DOI  :  10.1016/j.jcta.2005.12.001

来源: Elsevier

【 摘 要 】

Let w be an infinite word on an alphabet A. We denote by (n(i))(i >= 1) the increasing sequence (assumed to be infinite) of all lengths of palindromic prefixes of w. In this text, we give an explicit construction of all words w such that n(i+1) <= 2n(i)/ + 1 for all i, and study these words. Special examples include characteristic Sturmian words, and more generally standard episturmian words. As an application, we study the values taken by the quantity lim sup n(i+1)/n(i), and prove that it is minimal (among all nonperiodic words) for the Fibonacci word. (c) 2005 Elsevier Inc. All rights reserved.

【 授权许可】

Free