A generalized palindromization map in free monoids

Abstract

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^{*})\subseteq 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 $\varphi\circ \psi = \psi_X\circ \varphi$ for an injective morphism $\varphi$. Finally, we generalize $\psi_X$ by replacing palindromic closure with $\vartheta$-palindromic closure, where $\vartheta$ is any involutory antimorphism of $A^{*}$. This yields an extension of the class of $\vartheta$-standard words introduced by the authors in 2006.

Publication
Theoretical Computer Science