A generalized palindromization map in free monoids

作者：de Luca Aldo; De Luca Alessandro

来源：Theoretical Computer Science, 2012, 454: 109-128.

DOI：10.1016/j.tcs.2012.01.029

• Palindromic closure
• Episturmian words
• Arnoux-Rauzy words
• Generalized palindromization map
• Pseudopalindromes

The palindromization map psi in a free monoid A* was introduced in 1997 by the first author in the case of a binary alphabet A, and later extended by other authors to arbitrary alphabets. Acting on infinite words, psi generates the class of standard episturmian words, including standard Arnoux-Rauzy words. In this paper, we generalize the palindromization map, starting with a given code X over A. The new map psi(X) maps X* to the set PAL of palindromes of A*. In this way, some properties of psi are lost and some are saved in a weak form. When X has a finite deciphering delay, one can extend psi(X) to X-omega, generating a class of infinite words much wider than standard episturmian words. For a finite and maximal code X over A, we give a suitable generalization of standard Arnoux-Rauzy words, called X-AR words. We prove that any X-AR word is a morphic image of a standard Arnoux-Rauzy word and we determine some suitable linear lower and upper bounds to its factor complexity. For any code X, we say that psi(X) is conservative when psi(X)(X*) subset of X*. We study conservative maps psi(X) and conditions on X assuring that psi(X) is conservative. We also investigate the special case of morphic-conservative maps psi(X), i.e., maps such that phi circle psi = psi(X) circle phi for an injective morphism phi. Finally, we generalize psi(X) by replacing palindromic closure with theta-palindromic closure, where theta is any involutory antimorphism of A*. This yields an extension of the class of theta-standard words introduced by the authors in 2006.

• 出版日期2012-10-5