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.
2009
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]
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/359503
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
social impact