The finite graph problem for two-way alternating automata.

DOI10.1016/S0304-3975(02)00866-6MaRDI QIDQ1874281zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 1701347
• scientific article; zbMATH DE number 2086675
• A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
• scientific article; zbMATH DE number 1223729
• Alternating Tree Automata and Parity Games

Cites work

• Alternating tree automata
• Decidability of Second-Order Theories and Automata on Infinite Trees
• scientific article; zbMATH DE number 1223729 (Why is no real title available?)
• scientific article; zbMATH DE number 3339435 (Why is no real title available?)
• 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
• Modal languages and bounded fragments of predicate logic
• On the Restraining Power of Guards
• Results on the propositional \(\mu\)-calculus

Cited in

(6)

• scientific article; zbMATH DE number 1701347 (Why is no real title available?)
• Asymptotic Monadic Second-Order Logic
• A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
• scientific article; zbMATH DE number 2086675 (Why is no real title available?)
• Guarded negation
• Automata-theoretic characterisations of branching-time temporal logics

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1874281)