Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic.
Joseph Y. HalpernLeandro Chaves RêgoPublished in: IJCAI (2007)
Keyphrases
- modal logic
- temporal logic
- satisfiability problem
- mazurkiewicz traces
- decision procedures
- model checking
- pspace complete
- inference rules
- np complete
- classical logic
- sat problem
- nonmonotonic logics
- conditional logic
- belief revision
- np hard
- max sat
- situation calculus
- epistemic logic
- stochastic local search algorithms
- default logic
- stochastic local search
- computational complexity
- default reasoning
- explanation based generalization
- kripke models