Olivier Carton, Dominique Perrin, Jean-Éric Pin

Résumé : Cette article présente une synthèse de l'approche algébrique pour les automates acceptant des mots infinis. On discute de divers modes d'acceptation (automates de Büchi, automates de Muller, automate à transitions, reconnaissance faible par un semigroupe fini, omega-semigroupes) et on démontre leur équivalence. Nous donnons également deux preuves algébriques du théorème de McNaughton sur l'équivalence entre automates de Büchi et de Muller. Finalement, on présente des résultats récents sur les automates prophétiques et on discute leur extension aux mots profinis.

Abstract : This paper is a survey on the algebraic approach to the theory of automata accepting infinite words. We discuss the various acceptance modes (Büchi automata, Muller automata, transition automata, weak recognition by a finite semigroup, omega-semigroups) and prove their equivalence. We also give two algebraic proofs of McNaughton's theorem on the equivalence between Büchi and Muller automata. Finally, we present some recent work on prophetic automata and discuss its extension to transfinite words.