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

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

Bruyère Véronique , Carton Olivier, "Automata on Linear Orderings" in Journal of Computer & System Sciences, 73, 1--24

  • Edition : Academic Press
  • 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) 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.

Identifiants :
  • DOI : 10.1016/j.jcss.2006.10.009
  • ISSN : 0022-0000