Il s'agit de ma thèse de doctorat soutenue le 3 décembre 1993 à l'université Paris 7 devant le jury constitué de
Ce travail s'inscrit dans le cadre général de la théorie des automates et plus particulièrement des langages reconnaissables de mots infinis. Il étudie précisement les liens étroits entre la structure d'un automate et la complexité topologique du langage reconnu par cet automate.
Nous reprenons l'étude de la hiérarchie introduite par K. Wagner grâce aux ω-semigroupes récemment introduits par T. Wilke. Nous étendons les produits de Schützenberger et le produit en couronne aux ω-semigroupes. Nous obtenons alors pour les langages de mots infinis l'analogue des résultats classiques pour les langages de mots finis. Ces résultats nous permettent de donner une nouvelle preuve de l'équivalence entre les ω-semigroupes et les automates. Ces développements autorisent une présentation algébrique de la hiérarchie de Wagner. De cette nouvelle présentation résultent des caractérisations algébriques des classes de complexité et de nouvelles démonstrations pour les propriétés topologiques de cette hiérarchie.
À l'aide de diagrammes, nous établissons une nouvelle preuve d'un théorème de Hausdorff portant sur les chaînes d'ensembles. Ceci nous conduit à introduire une classe particulière d'automates de Rabin. Toutes les constructions pour les opérations booléennes se révèlent extrêmement simples pour ces automates. Ces derniers admettent en outre une réduction naturelle de leur condition d'acceptation : d'où une nouvelle caractérisation de l'indice de Rabin d'un langage de mots infinis.
This thesis is about finite automata and in particular about recognizable sets of infinite words. It studies the connections between the structure of an automaton and the topological complexity of the language recognized by the automaton.
We use ω-semigroups introduced by T. Wilke to study the Wagner's hierarchy. We extend to these algebras the Schützenberger product and the wreath product. We then obtain results similar to classical results for rational sets of finite words. We also give a new proof of the equivalence between automata and ω-semigroups. We give algebraic characterization of the Wagner's hierarchy and new proofs for the topological properties of this hierarchy.
We also introduce a new class of Rabin automata called chain automata. This class is large enough so that these automata have the same power as usual Rabin automata but many operations are effective when dealing with chain automata. This really contrasts with usual Rabin automata for which, simple operations like intersection are difficult tasks.