The Complexity of Enriched Mu-Calculi

DOI10.2168/LMCS-4(3:11)2008MaRDI QIDQ3535618zbMATH OpenFDO

Authors Carsten Lutz, Aniello Murano, Moshe Y. Vardi, P. A. Bonatti

Publication date 13 November 2008

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/LMCS-4(3:11)2008

zbMATH Keywords

automata modelscomplexitydecidabilityemptiness problemsexpressive fragmentsExpTime-completefully enriched \(\mu \)-calculussatisfiability

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Complexity of Enriched μ-Calculi
• scientific article; zbMATH DE number 2090317
• Enriched μ-Calculi Module Checking
• Enriched MU-Calculi Module Checking
• Complexity of the Lambek calculus and its fragments
• Enriched μ–Calculus Pushdown Module Checking
• Constructive completeness for the linear-time -calculus
• scientific article; zbMATH DE number 3845566
• Computer Science Logic
• On the complexity of purely complex μ computation and related problems in multidimensional systems

Cited in

(23)

• CTL^ with graded path modalities
• Cycle detection in computation tree logic
• Alternating-time temporal logics with linear past
• Mu-calculus satisfiability with arithmetic constraints
• Answering regular path queries in expressive description logics via alternating tree-automata
• Model-checking graded computation-tree logic with finite path semantics
• Some results on complexity of -calculus evaluation in the black-box model
• Reasoning about strategies: on the model-checking problem
• Reasoning About Substructures and Games
• The mu-calculus and Model Checking
• Querying regular graph patterns
• Reasoning with forest logic programs using fully enriched automata
• Enriched MU-Calculi Module Checking
• The Complexity of Enriched μ-Calculi
• scientific article; zbMATH DE number 1765663 (Why is no real title available?)
• Expressiveness and succinctness of a logic of robustness
• Reasoning and query answering in description logics
• scientific article; zbMATH DE number 7439738 (Why is no real title available?)
• Modal -calculus with atoms
• Enriched μ-Calculi Module Checking
• Presburger Büchi tree automata with applications to logics with expressive counting
• How to tell easy from hard: complexities of conjunctive query entailment in extensions of \(\mathcal{ALC}\)
• Decidable (ac)counting with Parikh and Muller: adding Presburger arithmetic to monadic second-order logic over tree-interpretable structures

This page was built for publication: The Complexity of Enriched Mu-Calculi

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