Intuitionistic implication makes model checking hard

Details Intuitionistic implication makes model checking hard Intuitionistic implication makes model checking hard

2011-07-11

arxiv.org/abs/1107.1963v3

LMCS 8 (2:3) 2012

Computer Science

Computational Complexity

29 pages, 10 figures

Scientific paper

10.2168/LMCS-8(2:3)2012

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.

Affiliated with

Also associated with

No associations

Rating

Intuitionistic implication makes model checking hard does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Intuitionistic implication makes model checking hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intuitionistic implication makes model checking hard will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137466