Parameterized complexity of weighted team definability

Research output: Contribution to journalArticleResearchpeer review

Authors

External Research Organisations

  • University of Helsinki
  • Heinz Nixdorf Institute
  • Paderborn University
View graph of relations

Details

Original languageEnglish
Pages (from-to)375-389
Number of pages15
JournalMathematical Structures in Computer Science
Volume34
Issue number5
Early online date20 Feb 2024
Publication statusPublished - 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

Cite this

Parameterized complexity of weighted team definability. / Kontinen, Juha; Mahmood, Yasir; Meier, Arne et al.
In: Mathematical Structures in Computer Science, Vol. 34, No. 5, 05.2024, p. 375-389.

Research output: Contribution to journalArticleResearchpeer review

Kontinen J, Mahmood Y, Meier A, Vollmer H. Parameterized complexity of weighted team definability. Mathematical Structures in Computer Science. 2024 May;34(5):375-389. Epub 2024 Feb 20. doi: 10.48550/arXiv.2302.00541, 10.1017/S0960129524000033
Kontinen, Juha ; Mahmood, Yasir ; Meier, Arne et al. / Parameterized complexity of weighted team definability. In: Mathematical Structures in Computer Science. 2024 ; Vol. 34, No. 5. pp. 375-389.
Download
@article{089f6a590d0c451a886ebaec4f6e32cd,
title = "Parameterized complexity of weighted team definability",
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",
author = "Juha Kontinen and Yasir Mahmood and Arne Meier and Heribert Vollmer",
note = "Publisher Copyright: {\textcopyright} The Author(s), 2024. Published by Cambridge University Press.",
year = "2024",
month = may,
doi = "10.48550/arXiv.2302.00541",
language = "English",
volume = "34",
pages = "375--389",
journal = "Mathematical Structures in Computer Science",
issn = "0960-1295",
publisher = "Cambridge University Press",
number = "5",

}

Download

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 -

By the same author(s)