The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs

DOI10.1016/j.tcs.2018.04.009zbMath1395.03009OpenAlexW2805621319MaRDI QIDQ1643142

Giacomo Lenzi, Giovanna D'Agostino

Publication date: 18 June 2018

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

Full work available at URL: http://hdl.handle.net/11390/1134879

zbMATH Keywords

parity gamesplanar graphsmodal \(\mu\)-calculusalternation hierarchy

Mathematics Subject Classification ID

Games involving graphs (91A43) Formal languages and automata (68Q45) Modal logic (including the logic of norms) (03B45) Planar graphs; geometric and topological aspects of graph theory (05C10) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• On the \(\mu \)-calculus over transitive and finite transitive frames
• Modal characterisation theorems over special classes of frames
• Results on the propositional \(\mu\)-calculus
• Propositional dynamic logic of regular programs
• The modal mu-calculus alternation hierarchy is strict
• Entanglement and the complexity of directed graphs
• On the Modal μ-Calculus Over Finite Symmetric Graphs
• The modalμ-calculus hierarchy over restricted classes of transition systems
• Monadic second order logic on tree-like structures
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• On modal  -calculus over reflexive symmetric graphs
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Alternating tree automata, parity games, and modal \(\mu\)-calculus
• On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic

This page was built for publication: The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs