Inproceedings: An article in a conference proceedings.
A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
Title of the conference
Selected Papers of the International Conference Infinity in Logic and Computation, Cape Town, South Africa, November 2007
Archibald M., Brattka V., Goranko V., Löwe B.
Lecture Notes in Computer Science
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
Web of science
Last modification date