Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Mundhenk, Martin; Weiß, Felix http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-30278
URL:

;

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

pdf-format:


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 =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2011.368},
  annote =	{Keywords: complexity, intuitionistic logic, model checking, ACi}
}

Keywords: complexity, intuitionistic logic, model checking, ACi
Seminar: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue date: 2011
Date of publication: 2011


DROPS-Home | Fulltext Search | Imprint Published by LZI