The modal mu-calculus alternation hierarchy is strict

DOI10.1016/S0304-3975(97)00217-XzbMATH Open0915.03017MaRDI QIDQ1276239FDOQ1276239

Julian Bradfield

Publication date: 20 January 1999

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

Recommendations

• The modal mu-calculus alternation hierarchy is strict
• The modal \(\mu \)-calculus hierarchy over restricted classes of transition systems
• The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
• scientific article; zbMATH DE number 1136070

zbMATH Keywords

temporal logicexpressivitymodal mu-calculusalternation hierarchyfixpoint properties

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45)

Cites Work

• Elementary induction on abstract structures
• A finite model theorem for the propositional \(\mu\)-calculus
• Results on the propositional \(\mu\)-calculus
• On model checking for the \(\mu\)-calculus and its fragments
• Title not available (Why is that?)
• An improved algorithm for the evaluation of fixpoint expressions
• An automata theoretic decision procedure for the propositional mu- calculus
• Title not available (Why is that?)
• The modal mu-calculus alternation hierarchy is strict
• On modal mu-calculus and Büchi tree automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the expressivity of the modal mu-calculus
• Programming languages and their definition. Selected papers ed. by C. B. Jones
• Title not available (Why is that?)
• Title not available (Why is that?)
• μ-definable sets of integers

Cited In (37)

• Mu-depth 3 is more than 2: A game-theoretic proof
• Title not available (Why is that?)
• The Descriptive Complexity of Parity Games
• On the universal and existential fragments of the \(\mu\)-calculus
• Symbolic Model Checking in Non-Boolean Domains
• Automata on infinite trees
• Model checking the full modal mu-calculus for infinite sequential processes
• Fixed point characterization of infinite behavior of finite-state systems
• The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs
• The mu-calculus and Model Checking
• Fixpoint alternation: arithmetic, transition systems, and the binary tree
• Yet another hierarchy theorem
• Title not available (Why is that?)
• The alternation hierarchy of the \(\mu \)-calculus over weakly transitive frames
• Canonical completeness of infinitary \(\mu \)
• The modal mu-calculus alternation hierarchy is strict
• A gap property of deterministic tree languages.
• On the expressive power of monadic least fixed point logic
• The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
• On the \(\mu \)-calculus over transitive and finite transitive frames
• On modal \(\mu\)-calculus with explicit interpolants
• Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
• The alternation hierarchy in fixpoint logic with chop is strict too
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• Free \(\mu\)-lattices
• Mu-calculus path checking
• The modal mu-calculus alternation hierarchy is strict
• Title not available (Why is that?)
• On the equational definition of the least prefixed point.
• On the Way to Alternating Weak Automata
• The modal \(\mu \)-calculus hierarchy over restricted classes of transition systems
• Model checking properties on reduced trace systems
• Ambiguous classes in \(\mu\)-calculi hierarchies
• $\aleph_1$ and the modal $\mu$-calculus
• Title not available (Why is that?)
• Deciding low levels of tree-automata hierarchy
• Fixpoints, games and the difference hierarchy

This page was built for publication: The modal mu-calculus alternation hierarchy is strict

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