Lyndon morphisms
type: Item
instance of: scholarly article
title: Lyndon morphisms
zbMATH Open document ID: 1101.68075
author: G. Richomme
published in: Bulletin of the Belgian Mathematical Society - Simon Stevin
publication date: 2005-06-09T00:00:00Z
full work available at URL: https://projecteuclid.org/euclid.bbms/1074791331
review text: 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.
reviewed by: Vesa Halava
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 2174594
zbMATH Keywords: combinatorics on words
zbMATH Keywords: morphisms
zbMATH Keywords: Lyndon words
zbMATH Keywords: Sturmian morphisms
zbMATH Keywords: lexicographic order
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2174594