serval:BIB_EEF86EFB69D9
A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
10.1007/978-3-642-03092-5_5
000277819200005
Duparc
J.
author
Facchini
A.
author
inproceedings
2009
Springer
Selected Papers of the International Conference Infinity in Logic and Computation, Cape Town, South Africa, November 2007
Archibald
M.
editor
Brattka
V.
editor
Goranko
V.
editor
Löwe
B.
editor
978-3-642-03091-8
Lecture Notes in Computer Science
conference publication
5489
46-55
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.
µ-calculus
Backward modalities
Wadge games
Topological complexity
Parity games
Two-way alternating tree automata
Descriptive set theory
eng
60_published
true
peer-reviewed
University of Lausanne
mailto:serval_help@unil.ch
http://www.unil.ch/serval
http://serval.unil.ch/disclaimer
https://serval.unil.ch/notice/serval:BIB_EEF86EFB69D9