Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 375-389 |
| Seitenumfang | 15 |
| Fachzeitschrift | Mathematical Structures in Computer Science |
| Jahrgang | 34 |
| Ausgabenummer | 5 |
| Frühes Online-Datum | 20 Feb. 2024 |
| Publikationsstatus | Veröffentlicht - Mai 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.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Mathematik (sonstige)
- Informatik (insg.)
- Angewandte Informatik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Mathematical Structures in Computer Science, Jahrgang 34, Nr. 5, 05.2024, S. 375-389.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › 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 -