On Quantified Propositional Logics and the Exponential Time Hierarchy

Miika Hannula
(Department of Computer Science, The University of Auckland)
Juha Kontinen
(Department of Mathematics and Statistics, University of Helsinki)
Martin Lück
(Institut für Theoretische Informatik, Leibniz Universität Hannover)
Jonni Virtema
(Department of Mathematics and Statistics, University of Helsinki)

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.

In Domenico Cantone and Giorgio Delzanno: Proceedings of the Seventh International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2016), Catania, Italy, 14-16 September 2016, Electronic Proceedings in Theoretical Computer Science 226, pp. 198–212.
Published: 13th September 2016.

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