A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
Details
State: Public
Version: author
Serval ID
serval:BIB_EEF86EFB69D9
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Institution
Title
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
Publisher
Springer
ISBN
978-3-642-03091-8
Publication state
Published
Issued date
2009
Peer-reviewed
Oui
Editor
Archibald M., Brattka V., Goranko V., Löwe B.
Volume
5489
Series
Lecture Notes in Computer Science
Pages
46-55
Language
english
Abstract
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.
Keywords
µ-calculus, Backward modalities, Wadge games, Topological complexity, Parity games, Two-way alternating tree automata, Descriptive set theory
Web of science
Open Access
Yes
Create date
18/03/2009 0:04
Last modification date
20/08/2019 17:16
Usage data
