Abstract FR:

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écisément 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 -semi-groupes récemment introduits par T. Wilkes. Nous étendons les produits de Schutzenberger et le produit en couronne aux -semi-groupes. 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 -semi-groupes 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. A 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 Rabin d'un langage de mots infinis