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

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

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

• 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?)
• 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
• 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)

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

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)