Details
Original language | English |
---|---|
Pages (from-to) | 375-389 |
Number of pages | 15 |
Journal | Mathematical Structures in Computer Science |
Volume | 34 |
Issue number | 5 |
Early online date | 20 Feb 2024 |
Publication status | Published - May 2024 |
Abstract
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 ϕ of central team-based logics. Given a first-order structure A and the parameter value k ∈ N as input, the question is to determine whether A, T |= ϕ 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.
Keywords
- dependence logic, descriptive complexity, inclusion logic, independence logic, Parameterized complexity, team semantics, weighted definability
ASJC Scopus subject areas
- Mathematics(all)
- Mathematics (miscellaneous)
- Computer Science(all)
- Computer Science Applications
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Mathematical Structures in Computer Science, Vol. 34, No. 5, 05.2024, p. 375-389.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Parameterized complexity of weighted team definability
AU - Kontinen, Juha
AU - Mahmood, Yasir
AU - Meier, Arne
AU - Vollmer, Heribert
N1 - Publisher Copyright: © The Author(s), 2024. Published by Cambridge University Press.
PY - 2024/5
Y1 - 2024/5
N2 - 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 ϕ of central team-based logics. Given a first-order structure A and the parameter value k ∈ N as input, the question is to determine whether A, T |= ϕ 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.
AB - 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 ϕ of central team-based logics. Given a first-order structure A and the parameter value k ∈ N as input, the question is to determine whether A, T |= ϕ 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.
KW - dependence logic
KW - descriptive complexity
KW - inclusion logic
KW - independence logic
KW - Parameterized complexity
KW - team semantics
KW - weighted definability
UR - http://www.scopus.com/inward/record.url?scp=85186550301&partnerID=8YFLogxK
U2 - 10.48550/arXiv.2302.00541
DO - 10.48550/arXiv.2302.00541
M3 - Article
VL - 34
SP - 375
EP - 389
JO - Mathematical Structures in Computer Science
JF - Mathematical Structures in Computer Science
SN - 0960-1295
IS - 5
ER -