A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
Détails
Etat: Public
Version: de l'auteur⸱e
ID Serval
serval:BIB_EEF86EFB69D9
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
A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
Titre de la conférence
Selected Papers of the International Conference Infinity in Logic and Computation, Cape Town, South Africa, November 2007
Editeur
Springer
ISBN
978-3-642-03091-8
Statut éditorial
Publié
Date de publication
2009
Peer-reviewed
Oui
Editeur⸱rice scientifique
Archibald M., Brattka V., Goranko V., Löwe B.
Volume
5489
Série
Lecture Notes in Computer Science
Pages
46-55
Langue
anglais
Résumé
Two-way alternating automata were introduced by Vardi in order to study the satisfiability problem for the modal μ-calculus extended with backwards modalities. In this paper, we present a very simple proof by way of Wadge games of the strictness of the hierarchy of Motowski indices of two-way alternating automata over trees.
Mots-clé
µ-calculus, Backward modalities, Wadge games, Topological complexity, Parity games, Two-way alternating tree automata, Descriptive set theory
Web of science
Open Access
Oui
Création de la notice
18/03/2009 0:04
Dernière modification de la notice
20/08/2019 17:16
Données d'usage
