Complexity of validity for propositional dependence logics

Jonni Virtema
(Japan Advanced Institute of Science and Technology and University of Tampere)

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.

In Adriano Peron and Carla Piazza: Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2014), Verona, Italy, 10th - 12th September 2014, Electronic Proceedings in Theoretical Computer Science 161, pp. 18–31.
Published: 24th August 2014.

ArXived at: https://dx.doi.org/10.4204/EPTCS.161.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org