by Olivier Carton
En s'appuyant sur le théorème des variétés qui a été prouvé pour les mots transfinis, nous donnons, dans cet article, trois exemples de correspondances entre des variétés de ω1-semigroupes finis et des variétés de ω1-langages. Nous caractérisons d'abord la classe des langages qui sont reconnus par des automates dans lesquels les transitions limites qui s'intersectent arrivent dans le même état. Il s'avère que la variété correspondante de ω1-semigroupes est définie par une équation qui a une interprétation topologique dans le cas des mots infinis. Elle caractérise les langages de mots infinis de la classe Δ2 = Π2 ∩ Σ2 de la hiérarchie de Borel. Ce résultat est utilisé pour prouver qu'un ω1-langage est reconnu par automate extensif si et seulement si sont ω1-semigroupe syntaxique est R-trivial et satisfait l'équation Δ2. Ce résultat étend celui d'Eilenberg à propos des semigroupes R-triviaux et les automates extensifs. Nous caractérisons finalement les ω1-langages reconnus par des automates extensifs dont les transitions limites sont triviales.
Following the recently proved variety theorem for transfinite words we give, in this paper, three instances of correspondence between varieties of finite ω1-semigroups and varieties of ω1-languages. We first characterize the class of languages which are recognized by automata in which overlapping limit transitions end in the same state. It turns out that the corresponding variety of ω1-semigroups is defined by an equation which has a topological interpretation in the case of infinite words. It characterizes languages of infinite words in the class Δ2 = Π2 ∩ Σ2 of the Borel hierarchy. This result is used to prove that an ω1-language is recognized by an extensive automaton if and only if its syntactic ω1-semigroup is R-trivial and satisfies the Δ2-equation. This result extends Eilenberg's result concerning R-trivial semigroups and extensive automata. We finally characterize ω1-languages recognized by extensive automata whose limit transitions are trivial.