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.



Valid HTML 4.01!