Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
- 17 April 1995
- journal article
- Published by Elsevier BV in Theoretical Computer Science
- Vol. 141 (1-2), 69-107
- https://doi.org/10.1016/0304-3975(94)00214-4
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- Infinite games played on finite graphsAnnals of Pure and Applied Logic, 1993
- Gurevich-Harrington's games defined by finite automataAnnals of Pure and Applied Logic, 1993
- Alternating automata, the weak monadic theory of trees and its complexityTheoretical Computer Science, 1992
- Extension of Gurevich-Harrington's restricted memory determinacy theorem: a criterion for the winning player and an explicit class of winning strategiesAnnals of Pure and Applied Logic, 1990
- Alternating automata on infinite treesTheoretical Computer Science, 1987
- Propositional dynamic logic of looping and converse is elementarily decidableInformation and Control, 1982
- Games People PlayUltrastructural Pathology, 1981
- Theory of ω-languagesI: Characterizations of ω-context-free languagesJournal of Computer and System Sciences, 1977
- Decidability of Second-Order Theories and Automata on Infinite TreesTransactions of the American Mathematical Society, 1969
- Testing and generating infinite sequences by a finite automatonInformation and Control, 1966