Alternating automata on infinite trees

DOI10.1016/0304-3975(87)90133-2zbMath0636.68108OpenAlexW1996207810MaRDI QIDQ1098325

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90133-2

zbMATH Keywords

infinite trees alternating automata on trees completion of nondeterministic automata

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

Related Items (53)

Ramsey-Based Inclusion Checking for Visibly Pushdown Automata ⋮ Complementation of Coalgebra Automata ⋮ Progress measures, immediate determinacy, and a subset construction for tree automata ⋮ Church's Problem Revisited ⋮ Complexity results on branching-time pushdown model checking ⋮ The mu-calculus and Model Checking ⋮ Knowledge base exchange: the case of OWL 2 QL ⋮ A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\) ⋮ From LTL to unambiguous Büchi automata via disambiguation of alternating automata ⋮ Determinization and memoryless winning strategies ⋮ Reasoning About Strategies ⋮ Fixed point characterization of infinite behavior of finite-state systems ⋮ On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic ⋮ A survey on satisfiability checking for the \(\mu \)-calculus through tree automata ⋮ From bidirectionality to alternation. ⋮ A gap property of deterministic tree languages. ⋮ A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings ⋮ Improved model checking of hierarchical systems ⋮ A space-efficient on-the-fly algorithm for real-time model checking ⋮ Unnamed Item ⋮ \textit{Once} and \textit{for all} ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Alternating automata with start formulas ⋮ Unnamed Item ⋮ The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity ⋮ An initial semantics for the \(\mu\)-calculus on trees and Rabin's complementation lemma ⋮ Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra ⋮ Alternating automata, the weak monadic theory of trees and its complexity ⋮ Visibly linear temporal logic ⋮ Completeness for the modal \(\mu\)-calculus: separating the combinatorics from the dynamics ⋮ Deciding low levels of tree-automata hierarchy ⋮ Answering regular path queries in expressive description logics via alternating tree-automata ⋮ Dynamic control with indistinguishable events ⋮ Decidability of infinite-state timed CCP processes and first-order LTL ⋮ An Automata-Theoretic Approach to Infinite-State Systems ⋮ Strategy logic ⋮ Distributive laws for the coinductive solution of recursive equations ⋮ On mathematical contributions of Paul E. Schupp ⋮ Theμ-calculus alternation-depth hierarchy is strict on binary trees ⋮ Converting a Büchi alternating automaton to a usual nondeterministic one ⋮ PDL with intersection and converse: satisfiability and infinite-state model checking ⋮ The Complexity of CTL* + Linear Past ⋮ Monoidal-closed categories of tree automata ⋮ Description Logics ⋮ Unnamed Item ⋮ BÜCHI COMPLEMENTATION MADE TIGHTER ⋮ Alternating automata: Unifying truth and validity checking for temporal logics ⋮ \( \omega \)-automata ⋮ Automata on infinite trees ⋮ Query inseparability for \(\mathcal{ALC}\) ontologies ⋮ SEMI-AUTOMATIC DISTRIBUTED SYNTHESIS ⋮ Uniform strategies, rational relations and jumping automata ⋮ Hierarchies of weak automata and weak monadic formulas

Cites Work

This page was built for publication: Alternating automata on infinite trees