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)
2009-04-01 - Article/Dans un journal avec peer-review - Anglais - 18 page(s)

Bruyère Véronique , Carton Olivier, Sénizergues Géraud, "Tree automata and automata on linear orderings" in RAIRO : Informatique Théorique et Applications = Theoretical Informatics and Applications, 43, 321-338

  • Edition : EDP Science
  • 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 show that the inclusion problem is decidable for rational languages of words indexed by scattered countable linear orderings. The method leans on a reduction to the decidability of the monadic second order theory of the infinite binary tree

Identifiants :
  • ISSN : 0988-3754
  • DOI : 10.1051/ita/2009009