The model checking problem for propositional intuitionistic logic with one variable is AC^1-complete

DOI10.4230/LIPICS.STACS.2011.368zbMATH Open1230.68145OpenAlexW2098830699MaRDI QIDQ3113702FDOQ3113702

Authors: Martin Mundhenk, Felix Weiss 

Publication date: 23 January 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_bd72.html

Recommendations

• An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic
• The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions
• Intuitionistic implication makes model checking hard
• scientific article; zbMATH DE number 2209833
• Complexity of intuitionistic propositional logic and its fragments

zbMATH Keywords

complexitymodel checkingintuitionistic logic\(\text{AC}^1\)

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60) Subsystems of classical logic (including intuitionistic logic) (03B20)

Cited In (2)

• The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions
• An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic

This page was built for publication: The model checking problem for propositional intuitionistic logic with one variable is \(\text{AC}^1\)-complete

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