by Véronique Bruyère and Olivier Carton
Dans un article précédent, nous avons introduit des automates et des expressions rationnelles pour les mots indexés par des ordres linéraires et nous avons montré un théorème de Kleene. Nous poursuivons ici ce travail en proposant une hiérarchie parmi ces ensembles rationnels. Chaque classe de cette hiérarchie par un sous-ensemble des opérations rationnelles qui sont autorisées. Nous caractérisons chacune de ces classes par une classe particulière d'automates, ce qui conduit à un théorème de Kleene pour chaque classe. Nous donnons également une caractérisons par des classes d'ordres.
In a preceeding paper, automata and rational expressions have been introduced for words indexed by linear orderings, together with a Kleene-like theorem. We here pursue this work by proposing a hierarchy among the rational sets. Each class of the hierarchy is defined by a subset of the rational operations that can be used. We then characterize any class by an appropriate class of automata, leading to a Kleene theorem inside the class. A characterization by particular classes of orderings is also given.