DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2005-09-01 - Article/Dans un journal avec peer-review - Anglais - 29 page(s)

Bruyère Véronique , Carton Olivier, "Hierarchy Among Automata on Linear Orderings" in Theory of Computing Systems, 38, 593-621

  • Edition : Springer Science & Business Media B.V., New York (NY)
  • Codes CREF : Théorie des graphes (DI1146), Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Informatique théorique (S829)
Texte intégral :

Abstract(s) :

(Anglais) In a preceding 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.