The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs
From MaRDI portal
Publication:1643142
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
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)
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
