Document Open Access Logo

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

Authors Martin Mundhenk, Felix Weiß



PDF
Thumbnail PDF

File

LIPIcs.STACS.2011.368.pdf
  • Filesize: 0.79 MB
  • 12 pages

Document Identifiers

Author Details

Martin Mundhenk
Felix Weiß

Cite AsGet BibTex

Martin Mundhenk and Felix Weiß. The model checking problem for propositional intuitionistic logic with one variable is AC^1-complete. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 368-379, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.STACS.2011.368

Abstract

We investigate the complexity of the model checking problem for propositional intuitionistic logic. We show that the model checking problem for intuitionistic logic with one variable is complete for logspace-uniform AC^1, and for intuitionistic logic with two variables it is P-complete. For superintuitionistic logics with one variable, we obtain NC^1-completeness for the model checking problem and for the tautology problem.
Keywords
  • complexity
  • intuitionistic logic
  • model checking
  • ACi

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail