A generalized palindromization map in free monoids

Abstract

The palindromization map $\psi$ in a free monoid $A^{\ast }$ 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^{\ast }$ to the set $PAL$ of palindromes of $A^{\ast }$. 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^{\ast })\subseteq X^{\ast }$. 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 $\varphi \circ \psi ={\psi }_X\circ \varphi$ for an injective morphism $\varphi$. Finally, we generalize ${\psi }_X$ by replacing palindromic closure with $\theta$-palindromic closure, where $\theta$ is any involutory antimorphism of $A^{\ast }$. This yields an extension of the class of $\theta$-standard words introduced by the authors in 2006.

Final version, accepted for publication on Theoret. Comput. Sci

References in corpus (1)

• A palindromization map for the free group

Cited by in corpus (1)

• Sturmian words and the Stern sequence