Coherence and Computational Complexity of Quantifier-free Dependence Logic Formulas |
| |
Authors: | Jarmo Kontinen |
| |
Institution: | 1. Bochum, Germany
|
| |
Abstract: | We study the computational complexity of the model checking problem for quantifier-free dependence logic ${(\mathcal{D})}$ formulas. We characterize three thresholds in the complexity: logarithmic space (LOGSPACE), non-deterministic logarithmic space (NL) and non-deterministic polynomial time (NP). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|