by Véronique Bruyère and Olivier Carton
Nous considérons dans cet article des mots indexés par des ordres linéaires. Ces mots généralisent les mots finis, les mots (bi-)infinis et les mots sur les ordinaux. Nous introduisons des automates et des expressions rationnelles pour ces mots. Nous prouvons que les deux notions coïncident pour les ordres linéaires qui sont dénombrables et dispersés. Ce résultat étend le théorème de Kleene.
We consider words indexed by linear orderings. These extend finite, (bi-)infinite words and words on ordinals. We introduce finite automata and rational expressions for these words. We prove that for countable scattered linear orderings, these two notions are equivalent. This result extends Kleene's theorem.