^_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.
• 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 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
• scientific article; zbMATH DE number 1670861 (Why is no real title available?)
• scientific article; zbMATH DE number 3960988 (Why is no real title available?)
• scientific article; zbMATH DE number 1304338 (Why is no real title available?)
• scientific article; zbMATH DE number 1136080 (Why is no real title available?)
• scientific article; zbMATH DE number 1954388 (Why is no real title available?)
• scientific article; zbMATH DE number 2080055 (Why is no real title available?)
• scientific article; zbMATH DE number 2102739 (Why is no real title available?)
• scientific article; zbMATH DE number 3339435 (Why is no real title available?)
• Rabin-Mostowski index problem: a step beyond deterministic 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)