Juha Kontinen

Tractability Frontier of Data Complexity in Team Semantics

2015 · arXiv (Cornell University)

We study the data complexity of model-checking for logics with team semantics. We focus on dependence, inclusion, and independence logic formulas under both strict and lax team semantics. Our results delineate a clear tractability/intractability frontiers …