Paper detail

A generalized palindromization map in free monoids

The palindromization map $ψ$ 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, $ψ$ 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 $ψ_X$ maps $X^*$ to the set $PAL$ of palindromes of $A^*$. In this way some properties of $ψ$ are lost and some are saved in a weak form. When $X$ has a finite deciphering delay one can extend $ψ_X$ to $X^ω$, 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 $ψ_X$ is conservative when $ψ_X(X^{*})\subseteq X^{*}$. We study conservative maps $ψ_X$ and conditions on $X$ assuring that $ψ_X$ is conservative. We also investigate the special case of morphic-conservative maps $ψ_{X}$, i.e., maps such that $ϕ\circ ψ= ψ_X\circ ϕ$ for an injective morphism $ϕ$. Finally, we generalize $ψ_X$ by replacing palindromic closure with $θ$-palindromic closure, where $θ$ is any involutory antimorphism of $A^*$. This yields an extension of the class of $θ$-standard words introduced by the authors in 2006.