Lyndon morphisms

In this paper the word morphisms which preserve lexicographic order are characterized. Assume that \(A\) \((=\{a_1,\dots, a_n\}\)) and \(B\) are two ordered alphabets, then \(f\colon A^* \to B^*\) is \textit{order-preserving} if, for all \(x,y\in A^*\), \(x\prec y\) implies \(f(x)\prec f(y)\) (where \(\prec\) is the lexicographic order induced by the order of the alphabet). It is proved that \(f\) is order-preserving iff \(\forall 1\leq i\leq n\), \(f(a_ia_n^{k_i})\prec f(a_{i+1})\), where \(k_i\) least integer such that \( | f(a_ia_n^{k_i})| \geq | f(a_{i+1})| \). The author also proves that no finite test set exists for detecting a morphisms being an order-preserving. A word \(w\) is a \textit{Lyndon word} if \(w=uv\) implies \(w\prec vu\), and a morphisms is a Lyndon morphisms if it preserves Lyndon words. A characterization for the Lyndon morphisms is given: \(f\) is Lyndon iff \(f\) is order-preserving and images of letters are Lyndon words. It is also proved that the monoid of endomorphisms is not finitely generated in the case of order-preserving and Lyndon morphisms, not even if they are assumed to be uniform. Episturmian morphisms are generalizations of the Sturmian morphisms, which define the Sturmian words. Also the episturmian order-preserving and Lyndon morphisms are characterized.

Recommendations

Cited in

(15)

This page was built for publication: Lyndon morphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1781929)