by Nicolas Bedon and Olivier Carton
Nous présentons dans cet article une approche algébrique de la théorie des langages de mots indéxés par les ordinaux dénombrables. La structure algébrique utilisée, appelée ω1-semigroupe, est une adaptation ce celle utilisée pour les langages rationnels de mots infinis. Nous montrons que les ω1-semigroupes finis sont équivalents aux automates. En particulier, la preuve donne un nouvel algorithme pour déterminiser un automate sur les ordinaux dénombrables. Comme dans le cas des mots infinis, un ω1-semigroupe syntaxique peut être associé à tout langages rationnels de mots indéxés par les ordinaux dénombrables. Ce résultat est utilisé pour démontrer un théorème à la Eilenberg. Il y a une correspondance bijective entre les variétés de ω1-langages rationnels et les pseudo-variétés de ω1-semigroupes finis.
We present in this paper an algebraic approach to the theory of languages of words on countable ordinals. The algebraic structure used, called an ω1-semigroup, is an adaptation of the one used in the theory of regular languages of ω-words. We show that finite ω1-semigroups are equivalent to automata. In particular, the proof gives a new algorithm for determinizing automata on countable ordinals. As in the cases of finite and ω-words, a syntactic ω1-semigroup can effectively be associated with any regular language of words on countable ordinals. This result is used to prove an Eilenberg type theorem. There is a one-to-one correspondence between varieties of regular ω1-languages and pseudo-varieties of ω1-semigroups.
PostScript Files