The -calculus alternation hierarchy collapses over structures with restricted connectivity

DOI10.1016/J.TCS.2014.03.027MaRDI QIDQ477204zbMATH OpenOpenAlexFDO

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

modal \(\mu\)-calculus alternation hierarchy fixpoints parity automata

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)

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

Cites work

scientific article; zbMATH DE number 3960988 (Why is no real title available?)
scientific article; zbMATH DE number 2080055 (Why is no real title available?)
scientific article; zbMATH DE number 1775458 (Why is no real title available?)
scientific article; zbMATH DE number 2102739 (Why is no real title available?)
scientific article; zbMATH DE number 5064388 (Why is no real title available?)
A linear-time model-checking algorithm for the alternation-free modal mu- calculus
Adding nesting structure to words
Alternating Automata and a Temporal Fixpoint Calculus for Visibly Pushdown Languages
Alternating automata on infinite trees
Alternating tree automata, parity games, and modal \(\mu\)-calculus
Fixpoint alternation: arithmetic, transition systems, and the binary tree
From linear time to branching time
Modal characterisation theorems over special classes of frames
On guarded transformation in the modal \(\mu\)-calculus
On modal mu-calculus and Büchi tree automata
On modal -calculus over reflexive symmetric graphs
On the \(\mu \)-calculus over transitive and finite transitive frames
On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
Regular languages of nested words: fixed points, automata, and synchronization
Results on the propositional \(\mu\)-calculus
Rudiments of \(\mu\)-calculus
The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
The modal \(\mu \)-calculus hierarchy over restricted classes of transition systems
The modal mu-calculus alternation hierarchy is strict
The tree width of auxiliary storage
Theμ-calculus alternation-depth hierarchy is strict on binary trees
Weak alternating automata are not that weak

Cited in

(14)

The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
Mu-depth 3 is more than 2: A game-theoretic proof
The arity hierarchy in the polyadic \(\mu\)-calculus
\(\mu\)-levels of interpolation
The alternation hierarchy of the \(\mu \)-calculus over weakly transitive frames
On modal \(\mu \)-calculus over finite graphs with small components or small tree width
A focus system for the alternation-free \(\mu \)-calculus
On modal \(\mu\)-calculus over finite graphs with bounded strongly connected components
scientific article; zbMATH DE number 1954388 (Why is no real title available?)
The modal mu-calculus alternation hierarchy is strict
Alternation is strict for higher-order modal fixpoint logic
STACS 2004
Describing the Wadge Hierarchy for the Alternation Free Fragment of μ-Calculus (I)
The modal \(\mu \)-calculus hierarchy over restricted classes of transition systems

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)