Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
From MaRDI portal
Publication:673778
DOI10.1016/0304-3975(94)00214-4zbMath0873.68135OpenAlexW2076284895MaRDI 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
Related Items (49)
Complete axiomatization and decidability of alternating-time temporal logic ⋮ Church's Problem Revisited ⋮ Baire Category Quantifier in Monadic Second Order Logic ⋮ Distributed synthesis for well-connected architectures ⋮ Automata Theory and Model Checking ⋮ Dicing on the Streett ⋮ Graded modalities in strategy logic ⋮ ON MODAL μ-CALCULUS OVER FINITE GRAPHS WITH SMALL COMPONENTS OR SMALL TREE WIDTH ⋮ Determinization and limit-determinization of Emerson-Lei automata ⋮ From LTL to unambiguous Büchi automata via disambiguation of alternating automata ⋮ Experiments with deterministic \(\omega\)-automata for formulas of linear temporal logic ⋮ Observations on determinization of Büchi automata ⋮ Model-checking iterated games ⋮ Reasoning About Strategies ⋮ Fixed point characterization of infinite behavior of finite-state systems ⋮ Towards a grand unification of Büchi complementation constructions ⋮ Reasoning about Quality and Fuzziness of Strategic Behaviors ⋮ Profile trees for Büchi word automata, with application to determinization ⋮ Distributed Synthesis for Alternating-Time Logics ⋮ Complexity of synthesis of composite service with correctness guarantee ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Unnamed Item ⋮ Completeness for \(\mu\)-calculi: a coalgebraic approach ⋮ New Optimizations and Heuristics for Determinization of Büchi Automata ⋮ Completeness for the modal \(\mu\)-calculus: separating the combinatorics from the dynamics ⋮ Visibly pushdown modular games ⋮ Answering regular path queries in expressive description logics via alternating tree-automata ⋮ Dynamic control with indistinguishable events ⋮ Automata and fixed point logic: a coalgebraic perspective ⋮ On mathematical contributions of Paul E. Schupp ⋮ Unnamed Item ⋮ Church’s Problem and a Tour through Automata Theory ⋮ A theory of ultimately periodic languages and automata with an application to time granularity ⋮ Tighter Bounds for the Determinisation of Büchi Automata ⋮ Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata ⋮ State of Büchi Complementation ⋮ Monoidal-closed categories of tree automata ⋮ Unnamed Item ⋮ Tool support for learning Büchi automata and linear temporal logic ⋮ On the Way to Alternating Weak Automata ⋮ Infinite games on finitely coloured graphs with applications to automata on infinite trees ⋮ Alternating automata: Unifying truth and validity checking for temporal logics ⋮ Automata on infinite trees ⋮ From liveness to promptness ⋮ A decidable class of problems for control under partial observation ⋮ SEMI-AUTOMATIC DISTRIBUTED SYNTHESIS ⋮ Relating word and tree automata ⋮ Projection for Büchi Tree Automata with Constraints between Siblings ⋮ Good-for-Game QPTL: An Alternating Hodges Semantics
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
This page was built for publication: Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
