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)

zbMATH Keywords

complexitydecidabilitysatisfiabilityautomata modelsemptiness problemsexpressive fragmentsExpTime-completefully enriched \(\mu \)-calculus

Mathematics Subject Classification ID

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

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 \(\mu \)-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)

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

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)