Coherence and computational complexity of quantifier-free dependence logic formulas

Authors
  • J. Kontinen
Publication date 2010
Host editors
  • J. Kontinen
  • J. Väänänen
Book title Proceedings of Dependence and Independence in Logic
Book subtitle ESSLLI 2010 Workshop : Copenhagen, August 16-20, 2010
Event ESSLLI 2010 workshop on Dependence and Independence in Logic, Copenhagen, Denmark
Pages (from-to) 58-77
Publisher Amsterdam: ILLC
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract We study the computational complexity of the model checking for quantifier-free dependence logic (D) formulas. We point out three thresholds in the computational complexity: logarithmic space, non- deterministic logarithmic space and non-deterministic polynomial time.
Document type Conference contribution
Language English
Published at
Permalink to this page
Back