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).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Fagin, Ronald, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, in R. Karp (ed.), Complexity of Computation, SIAM-AMS Proceedings 7, 1974, pp. 27–41.
Grädel, E., P. G. Kolaitis, and L. Libkin, Finite Model Theory And Its Applications, Springer, 2007.
Karp, R.M., Reducibility Among Combinatorial Problems, in R.E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, New York: Plenum, 1972, pp. 85–103.
Kontinen, Juha, and Jouko Väänänen, On Definability in Dependence logic, Journal of Logic, Language and Information, Volume 18, Nro. 3, 2009.
Papadimitriou, C. H., Computational Complexity, Addison Wesley, 1993.
Väänänen, Jouko, Dependence Logic: A New Approach to Independence Friendly Logic, Cambridge University Press, 2007.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kontinen, J. Coherence and Computational Complexity of Quantifier-free Dependence Logic Formulas. Stud Logica 101, 267–291 (2013). https://doi.org/10.1007/s11225-013-9481-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-013-9481-8