Relating word and tree automata

DOI10.1016/j.apal.2005.06.009zbMath1097.03034OpenAlexW2044854034MaRDI QIDQ2576943

Orna Kupferman, Moshe Y. Vardi, Shmuel Safra

Publication date: 29 December 2005

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2005.06.009

zbMATH Keywords

expressive powertree automataword automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

Unnamed Item, On the power of finite ambiguity in Büchi complementation, A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct, Minimization of automata for liveness languages, Unnamed Item, History-deterministic timed automata are not determinizable, Unnamed Item, On Synthesis of Specifications with Arithmetic, Unnamed Item, Minimizing GFG Transition-Based Automata, Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata, How Deterministic are Good-For-Games Automata?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Automata-theoretic techniques for modal logics of programs
• Complementing deterministic Büchi automata in polynomial time
• Reasoning about infinite computations
• On syntactic congruences for \(\omega\)-languages
• Efficient minimization of deterministic weak \(\omega\)-automata
• The complexity of verification
• Deciding Equivalence of Finite Tree Automata
• Deciding full branching time logic
• “Sometimes” and “not never” revisited
• The complexity of propositional linear temporal logics
• From linear time to branching time
• FINITE STATE PROCESSES, Z-TEMPORAL LOGIC AND THE MONADIC THEORY OF THE INTEGERS
• An automata-theoretic approach to branching-time model checking
• Automated Technology for Verification and Analysis
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Decision problems forω-automata
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees