In a recent paper with L. Q. Zamboni, the authors introduced the class of ϑ-episturmian words. An infinite word over A is standard ϑ-episturmian, where ϑ is an involutory antimorphism of A*, if its set of factors is closed under ϑ and its left special factors are prefixes. When ϑ is the reversal operator, one obtains the usual standard episturmian words. In this paper, we introduce and study ϑ-characteristic morphisms, that is, morphisms which map standard episturmian words into standard ϑ-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 ϑ-episturmian word is a morphic image, by an injective ϑ-characteristic morphism, of a standard episturmian word.
Characteristic morphisms of generalized episturmian words / Bucci, Michelangelo; DE LUCA, Aldo; DE LUCA, Alessandro. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 410:(2009), pp. 2840-2859. [10.1016/j.tcs.2008.12.001]
Characteristic morphisms of generalized episturmian words
BUCCI Michelangelo;DE LUCA Aldo
;DE LUCA Alessandro
2009
Abstract
In a recent paper with L. Q. Zamboni, the authors introduced the class of ϑ-episturmian words. An infinite word over A is standard ϑ-episturmian, where ϑ is an involutory antimorphism of A*, if its set of factors is closed under ϑ and its left special factors are prefixes. When ϑ is the reversal operator, one obtains the usual standard episturmian words. In this paper, we introduce and study ϑ-characteristic morphisms, that is, morphisms which map standard episturmian words into standard ϑ-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 ϑ-episturmian word is a morphic image, by an injective ϑ-characteristic morphism, of a standard episturmian word.File | Dimensione | Formato | |
---|---|---|---|
Cmogew.pdf
accesso aperto
Descrizione: preprint
Tipologia:
Documento in Pre-print
Licenza:
Creative commons
Dimensione
331.77 kB
Formato
Adobe PDF
|
331.77 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.