---
_id: '59911'
abstract:
- lang: eng
  text: "<jats:title>Abstract</jats:title><jats:p>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 <jats:inline-formula><jats:alternatives><jats:inline-graphic
    xmlns:xlink=\"http://www.w3.org/1999/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000033_inline1.png\"/><jats:tex-math>\r\n$\\varphi$\r\n</jats:tex-math></jats:alternatives></jats:inline-formula>
    of central team-based logics. Given a first-order structure <jats:inline-formula><jats:alternatives><jats:inline-graphic
    xmlns:xlink=\"http://www.w3.org/1999/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000033_inline2.png\"/><jats:tex-math>\r\n$\\mathcal{A}$\r\n</jats:tex-math></jats:alternatives></jats:inline-formula>
    and the parameter value <jats:inline-formula><jats:alternatives><jats:inline-graphic
    xmlns:xlink=\"http://www.w3.org/1999/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000033_inline3.png\"/><jats:tex-math>\r\n$k\\in
    \\mathbb N$\r\n</jats:tex-math></jats:alternatives></jats:inline-formula> as input,
    the question is to determine whether <jats:inline-formula><jats:alternatives><jats:inline-graphic
    xmlns:xlink=\"http://www.w3.org/1999/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000033_inline4.png\"/><jats:tex-math>\r\n$\\mathcal{A},T\\models
    \\varphi$\r\n</jats:tex-math></jats:alternatives></jats:inline-formula> for some
    team <jats:italic>T</jats:italic> of size <jats:italic>k</jats:italic>. 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.</jats:p>"
author:
- first_name: Juha
  full_name: Kontinen, Juha
  last_name: Kontinen
- first_name: Yasir
  full_name: Mahmood, Yasir
  id: '99353'
  last_name: Mahmood
- first_name: Arne
  full_name: Meier, Arne
  last_name: Meier
- first_name: Heribert
  full_name: Vollmer, Heribert
  last_name: Vollmer
citation:
  ama: Kontinen J, Mahmood Y, Meier A, Vollmer H. Parameterized complexity of weighted
    team definability. <i>Mathematical Structures in Computer Science</i>. 2024;34(5):375-389.
    doi:<a href="https://doi.org/10.1017/s0960129524000033">10.1017/s0960129524000033</a>
  apa: Kontinen, J., Mahmood, Y., Meier, A., &#38; Vollmer, H. (2024). Parameterized
    complexity of weighted team definability. <i>Mathematical Structures in Computer
    Science</i>, <i>34</i>(5), 375–389. <a href="https://doi.org/10.1017/s0960129524000033">https://doi.org/10.1017/s0960129524000033</a>
  bibtex: '@article{Kontinen_Mahmood_Meier_Vollmer_2024, title={Parameterized complexity
    of weighted team definability}, volume={34}, DOI={<a href="https://doi.org/10.1017/s0960129524000033">10.1017/s0960129524000033</a>},
    number={5}, journal={Mathematical Structures in Computer Science}, publisher={Cambridge
    University Press (CUP)}, author={Kontinen, Juha and Mahmood, Yasir and Meier,
    Arne and Vollmer, Heribert}, year={2024}, pages={375–389} }'
  chicago: 'Kontinen, Juha, Yasir Mahmood, Arne Meier, and Heribert Vollmer. “Parameterized
    Complexity of Weighted Team Definability.” <i>Mathematical Structures in Computer
    Science</i> 34, no. 5 (2024): 375–89. <a href="https://doi.org/10.1017/s0960129524000033">https://doi.org/10.1017/s0960129524000033</a>.'
  ieee: 'J. Kontinen, Y. Mahmood, A. Meier, and H. Vollmer, “Parameterized complexity
    of weighted team definability,” <i>Mathematical Structures in Computer Science</i>,
    vol. 34, no. 5, pp. 375–389, 2024, doi: <a href="https://doi.org/10.1017/s0960129524000033">10.1017/s0960129524000033</a>.'
  mla: Kontinen, Juha, et al. “Parameterized Complexity of Weighted Team Definability.”
    <i>Mathematical Structures in Computer Science</i>, vol. 34, no. 5, Cambridge
    University Press (CUP), 2024, pp. 375–89, doi:<a href="https://doi.org/10.1017/s0960129524000033">10.1017/s0960129524000033</a>.
  short: J. Kontinen, Y. Mahmood, A. Meier, H. Vollmer, Mathematical Structures in
    Computer Science 34 (2024) 375–389.
date_created: 2025-05-15T11:06:56Z
date_updated: 2025-05-15T11:07:08Z
department:
- _id: '574'
doi: 10.1017/s0960129524000033
intvolume: '        34'
issue: '5'
language:
- iso: eng
page: 375-389
publication: Mathematical Structures in Computer Science
publication_identifier:
  issn:
  - 0960-1295
  - 1469-8072
publication_status: published
publisher: Cambridge University Press (CUP)
status: public
title: Parameterized complexity of weighted team definability
type: journal_article
user_id: '99353'
volume: 34
year: '2024'
...