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

DOI10.4230/LIPICS.STACS.2011.368MaRDI QIDQ3113702zbMATH OpenOpenAlexFDO

Authors Martin Mundhenk, Felix Weiss

Publication date 23 January 2012

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

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)

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

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)