Displaying similar documents to “Automata accepting primitive words.”

On the simplest centralizer of a language

Paolo Massazza, Petri Salmela (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

Given a finite alphabet and a language , the centralizer of is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of (with respect to a lexicographic order) is prefix distinguishable in then the centralizer of is as simple as possible, that is, the submonoid . This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.