A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
| Data(s) |
2009
|
|---|---|
| Identificador |
https://serval.unil.ch/notice/serval:BIB_EEF86EFB69D9 https://serval.unil.ch/resource/serval:BIB_EEF86EFB69D9.P001/REF http://nbn-resolving.org/urn/resolver.pl?urn=urn:nbn:ch:serval-BIB_EEF86EFB69D97 urn:nbn:ch:serval-BIB_EEF86EFB69D97 |
| Idioma(s) |
eng |
| Publicador |
Springer |
| Direitos |
info:eu-repo/semantics/openAccess Copying allowed only for non-profit organizations https://serval.unil.ch/disclaimer |
| Fonte |
Selected Papers of the International Conference Infinity in Logic and Computation, Cape Town, South Africa, November 20075489 46-55 |
| Tipo |
info:eu-repo/semantics/conferenceObject inproceedings |
| Resumo |
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. |
| Formato |
application/pdf |
| Palavras-Chave | #µ-calculus; Backward modalities; Wadge games; Topological complexity; Parity games; Two-way alternating tree automata; Descriptive set theory |
