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

DOI10.1007/978-3-642-15349-5_10zbMATH Open1287.68110OpenAlexW1510869908MaRDI QIDQ3584967FDOQ3584967

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

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

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)

Cites Work

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

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
• Satisfiability and model checking for the logic of sub-intervals under the homogeneity assumption
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• The model checking problem for propositional intuitionistic logic with one variable is \(\text{AC}^1\)-complete
• Mathematical Foundations of Computer Science 2005
• The model checking fingerprints of CTL operators
• Title not available (Why is that?)

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)