Paper Info
Title
An AC 1-complete model checking problem for intuitionistic logic
Abstract
We show that the model checking problem for intuitionistic propositional logic with one variable is complete for logspace-uniform AC1. For superintuitionistic logics with one variable, we obtain NC1-completeness for the model checking problem.
Year
DOI
Venue
2014
10.1007/s00037-013-0062-z
Computational Complexity
Keywords
DocType
Volume
heyting algebra,03b20,06d20,model checking,ac 1,68q17,complexity,intuitionistic logic,Complexity,AC 1,AC,Heyting algebra,03B20,06D20,68Q17
Journal
23
Issue
ISSN
Citations 
4
1016-3328
0
PageRank 
References 
Authors
0.34
11
2
Name
Order
Citations
PageRank
Martin Mundhenk1232.95
Felix Weiss2142.43