License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.368
URN: urn:nbn:de:0030-drops-30278
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3027/
Mundhenk, Martin ;
Weiß, Felix
The model checking problem for propositional intuitionistic logic with one variable is AC^1-complete
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.
BibTeX - Entry
@InProceedings{mundhenk_et_al:LIPIcs:2011:3027,
author = {Martin Mundhenk and Felix Wei{\ss}},
title = {{The model checking problem for propositional intuitionistic logic with one variable is AC^1-complete}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {368--379},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-25-5},
ISSN = {1868-8969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3027},
URN = {urn:nbn:de:0030-drops-30278},
doi = {10.4230/LIPIcs.STACS.2011.368},
annote = {Keywords: complexity, intuitionistic logic, model checking, ACi}
}
|
Keywords: |
|
complexity, intuitionistic logic, model checking, ACi |
|
Collection: |
|
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) |
|
Issue Date: |
|
2011 |
|
Date of publication: |
|
11.03.2011 |
