Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra

DOI10.1016/0304-3975(94)00214-4zbMath0873.68135MaRDI QIDQ673778

Paul E. Schupp, David E. Muller

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00214-4

zbMATH Keywords

nondeterministic tree automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Church's Problem Revisited, Church’s Problem and a Tour through Automata Theory, A theory of ultimately periodic languages and automata with an application to time granularity, Distributed synthesis for well-connected architectures, Experiments with deterministic \(\omega\)-automata for formulas of linear temporal logic, Observations on determinization of Büchi automata, Tool support for learning Büchi automata and linear temporal logic, From liveness to promptness, A decidable class of problems for control under partial observation, Infinite games on finitely coloured graphs with applications to automata on infinite trees, Fixed point characterization of infinite behavior of finite-state systems, Complete axiomatization and decidability of alternating-time temporal logic, Dicing on the Streett, Automata and fixed point logic: a coalgebraic perspective, Relating word and tree automata, SEMI-AUTOMATIC DISTRIBUTED SYNTHESIS, Distributed Synthesis for Alternating-Time Logics, Tighter Bounds for the Determinisation of Büchi Automata, Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gurevich-Harrington's games defined by finite automata
• Extension of Gurevich-Harrington's restricted memory determinacy theorem: A criterion for the winning player and an explicit class of winning strategies
• Alternating automata on infinite trees
• Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
• Infinite games played on finite graphs
• Propositional dynamic logic of looping and converse is elementarily decidable
• Unforgettable Forgetful Determinacy
• FINITE STATE PROCESSES, Z-TEMPORAL LOGIC AND THE MONADIC THEORY OF THE INTEGERS
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees