Automata and semigroups recognizing infinite words
Olivier Carton, Dominique Perrin, Jean-Éric Pin · HAL (Le Centre pour la Communication Scientifique Directe) · 2007
This paper is a survey on the algebraic approach to the theory of automata accepting infinite words. We discuss the various acceptance modes (B"uchi automata, Muller automata, transition automata, weak recognition by a finite semigroup,!-semigroups) and prove their equivalence. We also give two algebraic proofs of McNaughton's theorem on the equivalence between B"uchi and Muller automata. Finally, we present some recent work on prophetic automata and discuss its extension to transfinite words.