## Lyndon morphisms.(English)Zbl 1101.68075

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 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 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.

### MSC:

 68R15 Combinatorics on words 20M35 Semigroups in automata theory, linguistics, etc. 05A05 Permutations, words, matrices
Full Text: