A purely algebraic proof of
McNaughton's theorem on infinite words
Bertrand Le Saec, Jean-Eric Pin et Pascal Weil
Résumé : Nous donnons une nouvelle preuve, purement
algébrique, du théorème de McNaughton sur les mots
infinis selon lequel tout ensemble reconnaissable X de mots infinis
peut être reconnu par un automate de Muller déterministe.
Notre preuve utilise la caractérisation de la
reconnaissabilité par les morphismes de semigroupes, et repose sur
certaines propriétés algébriques des semigroupes
finis. Nous obtenons également une solution simple du
problème de la construction d'un automate déterministe
reconnaissant X lorsqu'on connaît seulement un semigroupe
reconnaissant X.
Abstract : We give a new, purely algebraic proof of McNaughton's
theorem on infinite words, which states that each recognizable set X
of infinite words can be recognized by a deterministic Muller automaton.
Our proof uses the semigroup approach to recognizability and relies on
certain algebraic properties of finite semigroups. It also provides a
simple solution to the problem of finding a deterministic automaton for
X when one is given a semigroup recognizing X.