Hannula, M.; Kontinen, J.; Lück, M.; Virtema, J.: On quantified propositional logics and the exponential time hierarchy. In: Electronic Proceedings in Theoretical Computer Science, EPTCS 226 (2016), S. 198-212. DOI: https://doi.org/10.4204/EPTCS.226.14
Zusammenfassung: | |
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. | |
Lizenzbestimmungen: | CC BY 4.0 Unported |
Publikationstyp: | Article |
Publikationsstatus: | publishedVersion |
Erstveröffentlichung: | 2016 |
Die Publikation erscheint in Sammlung(en): | Fakultät für Elektrotechnik und Informatik |
Pos. | Land | Downloads | ||
---|---|---|---|---|
Anzahl | Proz. | |||
1 | Germany | 126 | 60,29% | |
2 | United States | 44 | 21,05% | |
3 | Sweden | 10 | 4,78% | |
4 | Greece | 9 | 4,31% | |
5 | China | 6 | 2,87% | |
6 | Taiwan | 2 | 0,96% | |
7 | Canada | 2 | 0,96% | |
8 | No geo information available | 1 | 0,48% | |
9 | Ukraine | 1 | 0,48% | |
10 | Thailand | 1 | 0,48% | |
andere | 7 | 3,35% |
Hinweis
Zur Erhebung der Downloadstatistiken kommen entsprechend dem „COUNTER Code of Practice for e-Resources“ international anerkannte Regeln und Normen zur Anwendung. COUNTER ist eine internationale Non-Profit-Organisation, in der Bibliotheksverbände, Datenbankanbieter und Verlage gemeinsam an Standards zur Erhebung, Speicherung und Verarbeitung von Nutzungsdaten elektronischer Ressourcen arbeiten, welche so Objektivität und Vergleichbarkeit gewährleisten sollen. Es werden hierbei ausschließlich Zugriffe auf die entsprechenden Volltexte ausgewertet, keine Aufrufe der Website an sich.