Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.60
URN: urn:nbn:de:0030-drops-64726
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6472/
Kontinen, Juha ; Kuusisto, Antti ; Virtema, Jonni
Decidability of Predicate Logics with Team Semantics
| pdf-format: |
|
Abstract
We study the complexity of predicate logics based on team semantics. We show that the satisfiability problems of two-variable independence logic and inclusion logic are both NEXPTIME-complete. Furthermore, we show that the validity problem of two-variable dependence logic is undecidable, thereby solving an open problem from the team semantics literature. We also briefly analyse the complexity of the Bernays-Schoenfinkel-Ramsey prefix classes of dependence logic.
BibTeX - Entry
@InProceedings{kontinen_et_al:LIPIcs:2016:6472,
author = {Juha Kontinen and Antti Kuusisto and Jonni Virtema},
title = {{Decidability of Predicate Logics with Team Semantics}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {60:1--60:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6472},
URN = {urn:nbn:de:0030-drops-64726},
doi = {10.4230/LIPIcs.MFCS.2016.60},
annote = {Keywords: team semantics, dependence logic, complexity, two-variable logic}
}
| Keywords: | team semantics, dependence logic, complexity, two-variable logic | |
| Seminar: | 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 19.08.2016 |
