1 results
Parameterized complexity of weighted team definability
-
- Journal:
- Mathematical Structures in Computer Science / Volume 34 / Issue 5 / May 2024
- Published online by Cambridge University Press:
- 20 February 2024, pp. 375-389
-
- Article
-
- You have access
- Open access
- HTML
- Export citation
-
In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analog of one of the most studied problems in parameterized complexity, the notion of weighted Fagin-definability, which is formulated in terms of satisfaction of first-order formulas with free relation variables. We focus on the parameterized complexity of weighted team definability for a fixed formula
$\varphi$ of central team-based logics. Given a first-order structure 
$\mathcal{A}$ and the parameter value 
$k\in \mathbb N$ as input, the question is to determine whether 
$\mathcal{A},T\models \varphi$ for some team T of size k. We show several results on the complexity of this problem for dependence, independence, and inclusion logic formulas. Moreover, we also relate the complexity of weighted team definability to the complexity classes in the well-known W-hierarchy as well as paraNP.
