Complexity of validity for propositional dependence logics

2014/06/30 by Jonni Virtema
Computer Science · #Accessibility relation #Autoepistemic logic #Intermediate logic #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Modal #Modal logic #Modal μ-calculus #Normal modal logic #Propositional calculus #Propositional variable #Semantic Web and Ontologies #cs.CC #cs.LO

paper · pdf · doi:10.4204/eptcs.161.5

published as EPTCS 161, 2014, pp. 18-31 · In Proceedings GandALF 2014, arXiv:1408.5560

openalex publication_date 2014/08/24 · arxiv created 2014/08/26 · arxiv updated 2016/06/21 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

Abstract

We study the validity problem for propositional dependence logic, modal dependence logic and extended modal dependence logic. We show that the validity problem for propositional dependence logic is NEXPTIME-complete. In addition, we establish that the corresponding problem for modal dependence logic and extended modal dependence logic is NEXPTIME-hard and in NEXPTIME^NP.

Citations

• Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification
• The complexity of theorem-proving procedures
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Inquisitive Logic