^_2 is decidable for ^_2

DOI10.1007/978-3-319-58741-7_28MaRDI QIDQ2011666zbMATH OpenOpenAlexFDO

Authors Karoliina Lehtinen, Sandra Quickert

Publication date 4 August 2017

Full work available at URL https://arxiv.org/abs/1703.03239

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Modal logic (including the logic of norms) (03B45)

Abstract: Given a $P{i}_2^{mu}$ formula of the modal $mu$ calculus, it is decidable whether it is equivalent to a $Sigm{a}_2^{mu}$ formula.

Cites work

• A gap property of deterministic tree languages.
• A hierarchy theorem for the -calculus
• Alternating tree automata, parity games, and modal -calculus
• An automata-theoretic approach to branching-time model checking
• Automata for the modal -calculus and related results
• Completeness of Kozen's axiomatisation of the propositional \(\mu\)-calculus.
• Deciding the first level of the -calculus alternation hierarchy
• Deciding the first levels of the modal alternation hierarchy by formula construction
• Deciding the topological complexity of Büchi languages
• Deciding the weak definability of Büchi definable tree languages
• Eliminating recursion in the -calculus
• scientific article; zbMATH DE number 3960988 (Why is no real title available?)
• scientific article; zbMATH DE number 3339435 (Why is no real title available?)
• Local model-checking of modal mu-calculus on acyclic labeled transition systems
• On deciding if deterministic Rabin language is in Büchi class
• Rabin-Mostowski index problem: a step beyond deterministic automata
• Relating hierarchies of word and tree automata
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• Theμ-calculus alternation-depth hierarchy is strict on binary trees

Cited in

(3)

• The descriptive complexity of modal model-checking games
• On the Way to Alternating Weak Automata
• Alternating weak automata from universal trees

This page was built for publication: \(\varSigma^{\mu}_2\) is decidable for \(\varPi^{\mu}_2\)

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