On the simplest centralizer of a language
Dipartimento di Informatica e Comunicazione,
Università degli Studi dell'Insubria,
via Mazzini 5, 21100 Varese, Italy;
2 Department of Mathematics and TUCS, University of Turku, 20014 Turku, Finland; firstname.lastname@example.org
Given a finite alphabet Σ and a language L ⊆ ∑+, the centralizer of L is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of L (with respect to a lexicographic order) is prefix distinguishable in L then the centralizer of L is as simple as possible, that is, the submonoid L*. This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.
Mathematics Subject Classification: 68Q70 / 68R15
Key words: Commutation equation / centralizer / lexicographic order.
© EDP Sciences, 2006