Semigroups and automata on infinite words

D. PERRIN, J-E. PIN

IBP-Litp 1994/14: Rapport de Recherche Litp / Litp research reports
26 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Semigroups and automata on infinite words

Résumé : Cet article est une introduction à la théorie algébrique des mots infinis. Il est axé sur les aspects combinatoires et algébriques de la théorie et est écrit dans la perspective de généraliser aux mots infinis les résultats connus sur les ensembles reconnaissables de mots finis. On commence par présenter l'équivalence entre automates de Muller et de Büchi, puis on étend aux mots infinis les caractérisations des parties reconnaissables utilisant des semigroupes finis. On poursuit l'analogie avec la théorie des mots finis jusqu'à l'obtention d'un analogue du théorème des variétés d'Eilenberg.

Abstract : This paper is an introduction to the algebraic theory of infinite words. It emphasizes the combinatorial and algebraic aspects of this theory and is written with the perspective of generalizing the results on recognizable sets of finite words to infinite words. The equivalence between Büchi automata and Muller automata is first presented. Then the theory of semigroups recognizing sets of finite words is extended to infinite words. The analogy with the theory for finite words is pushed sufficiently far to obtain a counterpart of Eilenberg's variety theorem for finite or infinite words.

Publications internes Litp 1994 / Litp research reports 1994