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

DOI10.1007/978-3-642-15349-5_10zbMath1287.68110OpenAlexW1510869908MaRDI QIDQ3584967

Martin Mundhenk, Felix Weiß

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) Modal logic (including the logic of norms) (03B45) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (3)

An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic ⋮ A note on the complexity of S4.2 ⋮ The model checking fingerprints of CTL operators

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Semantical investigations in Heyting's intuitionistic logic
• A propositional logic with explicit fixed points
• Propositional dynamic logic of regular programs
• The model checking problem for propositional intuitionistic logic with one variable is AC 1 -complete
• A polynomial translation of S4 into intuitionistic logic
• On formulas of one variable in intuitionistic propositional calculus
• Alternation
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Log Space Recognition and Translation of Parenthesis Languages
• Embeddings into Free Heyting Algebras and Translations into Intuitionistic Propositional Logic
• There are infinitely many Diodorean modal functions
• Modal Logics Between S 4 and S 5
• Logic and structure

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