2016/09/14 by Miika Hannula, Juha Kontinen, Martin Lück +1
Computer Science · #cs.LO
paper · pdf · doi:10.4204/eptcs.226.14
published as EPTCS 226, 2016, pp. 198-212 · In Proceedings GandALF 2016, arXiv:1609.03648
arxiv created 2016/09/14 · arxiv updated 2016/09/15
We study quantified propositional logics from the complexity theoretic point of view. First we introduce alternating dependency quantified boolean formulae (ADQBF) which generalize both quantified and dependency quantified boolean formulae. We show that the truth evaluation for ADQBF is AEXPTIME(poly)-complete. We also identify fragments for which the problem is complete for the levels of the exponential hierarchy. Second we study propositional team-based logics. We show that DQBF formulae correspond naturally to quantified propositional dependence logic and present a general NEXPTIME upper bound for quantified propositional logic with a large class of generalized dependence atoms. Moreover we show AEXPTIME(poly)-completeness for extensions of propositional team logic with generalized dependence atoms.