SIMULATING ALTERNATING TREE AUTOMATA BY NONDETERMINISTIC AUTOMATA - NEW RESULTS AND NEW PROOFS OF THE THEOREMS OF RABIN, MCNAUGHTON AND SAFRA

Authors
MULLER DE SCHUPP PE
Citation
De. Muller et Pe. Schupp, SIMULATING ALTERNATING TREE AUTOMATA BY NONDETERMINISTIC AUTOMATA - NEW RESULTS AND NEW PROOFS OF THE THEOREMS OF RABIN, MCNAUGHTON AND SAFRA, Theoretical computer science, 141(1-2), 1995, pp. 69-107
Citations number
24
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
141
Issue
1-2
Year of publication
1995
Pages
69 - 107
Database
ISI
SICI code
0304-3975(1995)141:1-2<69:SATABN>2.0.ZU;2-Z
Abstract
We give a proof that alternating tree automata can be simulated by non deterministic tree automata which yields new complexity results and a unified proof of the theorems of Rabin, McNaughton and Safra. We also give a simple axiomatic framework for uniformizing strategies.