The finite graph problem for two-way alternating automata.

DOI10.1016/S0304-3975(02)00866-6zbMath1052.68069OpenAlexW2658457120MaRDI QIDQ1874281

Mikołaj Bojańczyk

Publication date: 25 May 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00866-6

zbMATH Keywords

\(\mu\)-calculusAlternating automataFinite model

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modal logic (including the logic of norms) (03B45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items (2)

Asymptotic Monadic Second-Order Logic ⋮ Guarded Negation

Cites Work

• Unnamed Item
• Unnamed Item
• Results on the propositional \(\mu\)-calculus
• Alternating tree automata
• Modal languages and bounded fragments of predicate logic
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Loosely guarded fragment of first-order logic has the finite model property
• On the Restraining Power of Guards
• Decidability of Second-Order Theories and Automata on Infinite Trees

This page was built for publication: The finite graph problem for two-way alternating automata.