The -calculus alternation hierarchy collapses over structures with restricted connectivity
DOI10.1016/J.TCS.2014.03.027zbMATH Open1327.03016OpenAlexW2962706960MaRDI QIDQ477204FDOQ477204
Authors: Julian Gutiérrez, Felix Klaedtke, Martin Lange 
Publication date: 2 December 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.03.027
Recommendations
- The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
- The modal \(\mu \)-calculus hierarchy over restricted classes of transition systems
- On modal \(\mu\)-calculus over finite graphs with bounded strongly connected components
- The modal mu-calculus alternation hierarchy is strict
- The modal mu-calculus alternation hierarchy is strict
Applications of graph theory (05C90) Directed graphs (digraphs), tournaments (05C20) Modal logic (including the logic of norms) (03B45) Automata and formal grammars in connection with logical questions (03D05)
Cites Work
- Adding nesting structure to words
- On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
- Results on the propositional \(\mu\)-calculus
- Alternating automata on infinite trees
- Alternating tree automata, parity games, and modal \(\mu\)-calculus
- Weak alternating automata are not that weak
- Title not available (Why is that?)
- A linear-time model-checking algorithm for the alternation-free modal mu- calculus
- The tree width of auxiliary storage
- The modal mu-calculus alternation hierarchy is strict
- On modal mu-calculus and Büchi tree automata
- Alternating Automata and a Temporal Fixpoint Calculus for Visibly Pushdown Languages
- The modal \(\mu \)-calculus hierarchy over restricted classes of transition systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- On guarded transformation in the modal \(\mu\)-calculus
- Title not available (Why is that?)
- Theμ-calculus alternation-depth hierarchy is strict on binary trees
- Fixpoint alternation: arithmetic, transition systems, and the binary tree
- The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
- From linear time to branching time
- On modal -calculus over reflexive symmetric graphs
- Title not available (Why is that?)
- Rudiments of \(\mu\)-calculus
- On the \(\mu \)-calculus over transitive and finite transitive frames
- Regular languages of nested words: fixed points, automata, and synchronization
- Modal characterisation theorems over special classes of frames
Cited In (14)
- Mu-depth 3 is more than 2: A game-theoretic proof
- On modal \(\mu \)-calculus over finite graphs with small components or small tree width
- \(\mu\)-levels of interpolation
- Describing the Wadge Hierarchy for the Alternation Free Fragment of μ-Calculus (I)
- The alternation hierarchy of the \(\mu \)-calculus over weakly transitive frames
- The modal mu-calculus alternation hierarchy is strict
- The arity hierarchy in the polyadic \(\mu\)-calculus
- The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
- STACS 2004
- On modal \(\mu\)-calculus over finite graphs with bounded strongly connected components
- A focus system for the alternation-free \(\mu \)-calculus
- Title not available (Why is that?)
- The modal \(\mu \)-calculus hierarchy over restricted classes of transition systems
- Alternation is strict for higher-order modal fixpoint logic
This page was built for publication: The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477204)
