Paper Info
Title
Decidability of Predicate Logics with Team Semantics.
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.
Year
DOI
Venue
2016
10.4230/LIPIcs.MFCS.2016.60
mathematical foundations of computer science
Field
DocType
Volume
Discrete mathematics,T-norm fuzzy logics,Predicate variable,Description logic,Algorithm,Theoretical computer science,Classical logic,Predicate functor logic,Predicate logic,Well-founded semantics,Higher-order logic,Mathematics
Conference
58
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Juha Kontinen117624.67
Antti Kuusisto27215.69
Jonni Virtema37911.93