Characteristic morphisms of generalized episturmian words

Abstract

In a recent paper with L. Q. Zamboni, the authors introduced the class of $\vartheta$-episturmian words. An infinite word over $A$ is standard $\vartheta$-episturmian, where $\vartheta$ is an involutory antimorphism of $A^{*}$, if its set of factors is closed under $\vartheta$ and its left special factors are prefixes. When $\vartheta$ is the reversal operator, one obtains the usual standard episturmian words. In this paper, we introduce and study $\vartheta$-characteristic morphisms, that is, morphisms which map standard episturmian words into standard $\vartheta$-episturmian words. They are a natural extension of standard episturmian morphisms. The main result of the paper is a characterization of these morphisms when they are injective. In order to prove this result, we also introduce and study a class of biprefix codes which are overlap-free, i.e., any two code words do not overlap properly, and normal, i.e., no proper suffix (prefix) of any code-word is left (right) special in the code. A further result is that any standard $\vartheta$-episturmian word is a morphic image, by an injective $\vartheta$-characteristic morphism, of a standard episturmian word.

Publication
Theoretical Computer Science