Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata

Détails

Ressource 1Télécharger: BIB_1B41D2F54A21.P001.pdf (232.51 [Ko])
Etat: Public
Version: de l'auteur⸱e
ID Serval
serval:BIB_1B41D2F54A21
Type
Actes de conférence (partie): contribution originale à la littérature scientifique, publiée à l'occasion de conférences scientifiques, dans un ouvrage de compte-rendu (proceedings), ou dans l'édition spéciale d'un journal reconnu (conference proceedings).
Collection
Publications
Institution
Titre
Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
Titre de la conférence
Computer Science Logic: 23rd International Workshop, CSL 2009, 18th Annual Conference of the EACSL, Coimbra, Portugal, September 7-11, 2009, Proceedings
Auteur⸱e⸱s
Duparc J., Facchini A., Murlak F.
Editeur
Springer
ISBN
978-3-642-04026-9
Statut éditorial
Publié
Date de publication
2009
Peer-reviewed
Oui
Editeur⸱rice scientifique
Grädel E., Kahle R.
Volume
5771
Série
Lecture Notes in Computer Science
Pages
225-239
Langue
anglais
Résumé
For deterministic tree automata, classical hierarchies, like Mostowski-Rabin (or index) hierarchy, Borel hierarchy, or Wadge hierarchy, are known to be decidable. However, when it comes to non-deterministic tree automata, none of these hierarchies is even close to be understood. Here we make an attempt in paving the way towards a clear understanding of tree automata. We concentrate on the class of linear game automata (LGA), and prove within this new context, that all corresponding hierarchies mentioned above—Mostowski-Rabin, Borel, and Wadge—are decidable. The class LGA is obtained by taking linear tree automata with alternation restricted to the choice of path in the input tree. Despite their simplicity, LGA recognize sets of arbitrary high Borel rank. The actual richness of LGA is revealed by the height of their Wadge hierarchy: (ω^ω)^ω.
Mots-clé
Linear tree automata, Wadge Hierarchy, Index Problem, Borel Hierarchy
Web of science
Création de la notice
21/09/2009 12:09
Dernière modification de la notice
20/08/2019 13:52
Données d'usage