Martin Mundhenk ; Felix Weiss - Intuitionistic implication makes model checking hard

lmcs:1160 - Logical Methods in Computer Science, April 27, 2012, Volume 8, Issue 2 - https://doi.org/10.2168/LMCS-8(2:3)2012
Intuitionistic implication makes model checking hardArticle

Authors: Martin Mundhenk ; Felix Weiss

    We investigate the complexity of the model checking problem for intuitionistic and modal propositional logics over transitive Kripke models. More specific, we consider intuitionistic logic IPC, basic propositional logic BPL, formal propositional logic FPL, and Jankov's logic KC. We show that the model checking problem is P-complete for the implicational fragments of all these intuitionistic logics. For BPL and FPL we reach P-hardness even on the implicational fragment with only one variable. The same hardness results are obtained for the strictly implicational fragments of their modal companions. Moreover, we investigate whether formulas with less variables and additional connectives make model checking easier. Whereas for variable free formulas outside of the implicational fragment, FPL model checking is shown to be in LOGCFL, the problem remains P-complete for BPL.


    Volume: Volume 8, Issue 2
    Published on: April 27, 2012
    Imported on: July 6, 2011
    Keywords: Computer Science - Computational Complexity,03B20, 68Q15, 68Q17

    Publications

    Has review
    • 1 zbMATH Open

    1 Document citing this article

    Consultation statistics

    This page has been seen 1479 times.
    This article's PDF has been downloaded 441 times.