The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions

DOI10.1007/978-3-642-15349-5_10MaRDI QIDQ3584967zbMATH OpenOpenAlexFDO

Authors Martin Mundhenk, Felix Weiss

Publication date 31 August 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15349-5_10

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Modal logic (including the logic of norms) (03B45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Model checking for modal intuitionistic dependence logic
• Complexity of model checking for modal dependence logic
• Complexity of model checking for logics over Kripke models
• An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic
• The Complexity of Model Checking Higher-Order Fixpoint Logic
• scientific article; zbMATH DE number 2163033
• Mathematical Foundations of Computer Science 2005
• Model checking and validity in propositional and modal inclusion logics
• Model checking and validity in propositional and modal inclusion logics
• Computer Science Logic

Cites work

• A polynomial translation of S4 into intuitionistic logic
• A propositional logic with explicit fixed points
• Alternation
• Complexity of intuitionistic and Visser's basic and formal logics in finitely many variables
• Embeddings into Free Heyting Algebras and Translations into Intuitionistic Propositional Logic
• scientific article; zbMATH DE number 1003731 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 757645 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Log Space Recognition and Translation of Parenthesis Languages
• Logic and structure
• Modal Logics Between S 4 and S 5
• On formulas of one variable in intuitionistic propositional calculus
• Propositional dynamic logic of regular programs
• Semantical investigations in Heyting's intuitionistic logic
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The model checking problem for propositional intuitionistic logic with one variable is \(\text{AC}^1\)-complete
• There are infinitely many Diodorean modal functions

Cited in

(12)

• A note on model checking the modal \(\nu\)-calculus
• The model checking fingerprints of CTL operators
• Complexity of model checking for cardinality-based belief revision operators
• Universal guards, relativization of quantifiers, and failure models in model checking modulo theories
• Intuitionistic implication makes model checking hard
• The model checking problem for propositional intuitionistic logic with one variable is \(\text{AC}^1\)-complete
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic
• scientific article; zbMATH DE number 1884382 (Why is no real title available?)
• Satisfiability and model checking for the logic of sub-intervals under the homogeneity assumption
• A note on the complexity of \textbf{S4.2}
• Mathematical Foundations of Computer Science 2005

This page was built for publication: The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions

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