---
_id: '61874'
abstract:
- lang: eng
  text: "<jats:p>\r\n            We study descriptive complexity of counting complexity
    classes in the range from #P to\r\n            <jats:inline-formula content-type=\"math/tex\">\r\n
    \             <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\({\\text{#}\\!\\cdot\\!\\text{NP}}\\)</jats:tex-math>\r\n
    \           </jats:inline-formula>\r\n            . The proof of Fagin’s characterization
    of NP by existential second-order logic generalizes to the counting setting in
    the following sense: The class #P can be logically described as the class of functions
    counting satisfying assignments to free relation variables in first-order formulae.
    This was first observed by Saluja et al. (1995). In this paper we extend this
    study to classes beyond #P and extensions of first-order logic with team semantics.
    These team-based logics are closely related to existential second-order logic
    and its fragments, hence our results also shed light on the complexity of counting
    for extensions of first-order logic in Tarski’s semantics. Our results show that
    the class\r\n            <jats:inline-formula content-type=\"math/tex\">\r\n              <jats:tex-math
    notation=\"LaTeX\" version=\"MathJax\">\\({\\text{#}\\!\\cdot\\!\\text{NP}}\\)</jats:tex-math>\r\n
    \           </jats:inline-formula>\r\n            can be logically characterized
    by independence logic and existential second-order logic, whereas dependence logic
    and inclusion logic give rise to subclasses of\r\n            <jats:inline-formula
    content-type=\"math/tex\">\r\n              <jats:tex-math notation=\"LaTeX\"
    version=\"MathJax\">\\({\\text{#}\\!\\cdot\\!\\text{NP}}\\)</jats:tex-math>\r\n
    \           </jats:inline-formula>\r\n            and #P , respectively. We further
    relate the class obtained from inclusion logic to the complexity class\r\n            <jats:inline-formula
    content-type=\"math/tex\">\r\n              <jats:tex-math notation=\"LaTeX\"
    version=\"MathJax\">\\({\\text{TotP}} \\subseteq{\\text{#P}}\\)</jats:tex-math>\r\n
    \           </jats:inline-formula>\r\n            .\r\n          </jats:p>"
article_number: '3771721'
author:
- first_name: Anselm
  full_name: Haak, Anselm
  id: '109969'
  last_name: Haak
- first_name: Juha
  full_name: Kontinen, Juha
  last_name: Kontinen
- first_name: Fabian
  full_name: Müller, Fabian
  last_name: Müller
- first_name: Heribert
  full_name: Vollmer, Heribert
  last_name: Vollmer
- first_name: Fan
  full_name: Yang, Fan
  last_name: Yang
citation:
  ama: Haak A, Kontinen J, Müller F, Vollmer H, Yang F. Counting of Teams in First-Order
    Team Logics. <i>ACM Transactions on Computational Logic</i>. Published online
    2025. doi:<a href="https://doi.org/10.1145/3771721">10.1145/3771721</a>
  apa: Haak, A., Kontinen, J., Müller, F., Vollmer, H., &#38; Yang, F. (2025). Counting
    of Teams in First-Order Team Logics. <i>ACM Transactions on Computational Logic</i>,
    Article 3771721. <a href="https://doi.org/10.1145/3771721">https://doi.org/10.1145/3771721</a>
  bibtex: '@article{Haak_Kontinen_Müller_Vollmer_Yang_2025, title={Counting of Teams
    in First-Order Team Logics}, DOI={<a href="https://doi.org/10.1145/3771721">10.1145/3771721</a>},
    number={3771721}, journal={ACM Transactions on Computational Logic}, publisher={Association
    for Computing Machinery (ACM)}, author={Haak, Anselm and Kontinen, Juha and Müller,
    Fabian and Vollmer, Heribert and Yang, Fan}, year={2025} }'
  chicago: Haak, Anselm, Juha Kontinen, Fabian Müller, Heribert Vollmer, and Fan Yang.
    “Counting of Teams in First-Order Team Logics.” <i>ACM Transactions on Computational
    Logic</i>, 2025. <a href="https://doi.org/10.1145/3771721">https://doi.org/10.1145/3771721</a>.
  ieee: 'A. Haak, J. Kontinen, F. Müller, H. Vollmer, and F. Yang, “Counting of Teams
    in First-Order Team Logics,” <i>ACM Transactions on Computational Logic</i>, Art.
    no. 3771721, 2025, doi: <a href="https://doi.org/10.1145/3771721">10.1145/3771721</a>.'
  mla: Haak, Anselm, et al. “Counting of Teams in First-Order Team Logics.” <i>ACM
    Transactions on Computational Logic</i>, 3771721, Association for Computing Machinery
    (ACM), 2025, doi:<a href="https://doi.org/10.1145/3771721">10.1145/3771721</a>.
  short: A. Haak, J. Kontinen, F. Müller, H. Vollmer, F. Yang, ACM Transactions on
    Computational Logic (2025).
date_created: 2025-10-17T09:43:42Z
date_updated: 2025-10-17T09:44:06Z
department:
- _id: '888'
doi: 10.1145/3771721
language:
- iso: eng
publication: ACM Transactions on Computational Logic
publication_identifier:
  issn:
  - 1529-3785
  - 1557-945X
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: Counting of Teams in First-Order Team Logics
type: journal_article
user_id: '109969'
year: '2025'
...
---
_id: '54577'
abstract:
- lang: eng
  text: '<jats:p>Argumentation is a well-established formalism dealing with conflicting
    information by generating and comparing arguments. It has been playing a major
    role in AI for decades. In logic-based argumentation, we explore the internal
    structure of an argument. Informally, a set of formulas is the support for a given
    claim if it is consistent, subset-minimal, and implies the claim. In such a case,
    the pair of the support and the claim together is called an argument. In this
    article, we study the propositional variants of the following three computational
    tasks studied in argumentation: ARG (exists a support for a given claim with respect
    to a given set of formulas), ARG-Check (is a given set a support for a given claim),
    and ARG-Rel (similarly as ARG plus requiring an additionally given formula to
    be contained in the support). ARG-Check is complete for the complexity class DP,
    and the other two problems are known to be complete for the second level of the
    polynomial hierarchy (Creignou et al. 2014 and Parson et al., 2003) and, accordingly,
    are highly intractable. Analyzing the reason for this intractability, we perform
    a two-dimensional classification: First, we consider all possible propositional
    fragments of the problem within Schaefer’s framework (STOC 1978) and then study
    different parameterizations for each of the fragments. We identify a list of reasonable
    structural parameters (size of the claim, support, knowledge base) that are connected
    to the aforementioned decision problems. Eventually, we thoroughly draw a fine
    border of parameterized intractability for each of the problems showing where
    the problems are fixed-parameter tractable and when this exactly stops. Surprisingly,
    several cases are of very high intractability (para-NP and beyond).</jats:p>'
author:
- first_name: Yasir
  full_name: Mahmood, Yasir
  id: '99353'
  last_name: Mahmood
- first_name: Arne
  full_name: Meier, Arne
  last_name: Meier
- first_name: Johannes
  full_name: Schmidt, Johannes
  last_name: Schmidt
citation:
  ama: Mahmood Y, Meier A, Schmidt J. Parameterized Complexity of Logic-based Argumentation
    in Schaefer’s Framework. <i>ACM Transactions on Computational Logic</i>. 2023;24(3):1-25.
    doi:<a href="https://doi.org/10.1145/3582499">10.1145/3582499</a>
  apa: Mahmood, Y., Meier, A., &#38; Schmidt, J. (2023). Parameterized Complexity
    of Logic-based Argumentation in Schaefer’s Framework. <i>ACM Transactions on Computational
    Logic</i>, <i>24</i>(3), 1–25. <a href="https://doi.org/10.1145/3582499">https://doi.org/10.1145/3582499</a>
  bibtex: '@article{Mahmood_Meier_Schmidt_2023, title={Parameterized Complexity of
    Logic-based Argumentation in Schaefer’s Framework}, volume={24}, DOI={<a href="https://doi.org/10.1145/3582499">10.1145/3582499</a>},
    number={3}, journal={ACM Transactions on Computational Logic}, publisher={Association
    for Computing Machinery (ACM)}, author={Mahmood, Yasir and Meier, Arne and Schmidt,
    Johannes}, year={2023}, pages={1–25} }'
  chicago: 'Mahmood, Yasir, Arne Meier, and Johannes Schmidt. “Parameterized Complexity
    of Logic-Based Argumentation in Schaefer’s Framework.” <i>ACM Transactions on
    Computational Logic</i> 24, no. 3 (2023): 1–25. <a href="https://doi.org/10.1145/3582499">https://doi.org/10.1145/3582499</a>.'
  ieee: 'Y. Mahmood, A. Meier, and J. Schmidt, “Parameterized Complexity of Logic-based
    Argumentation in Schaefer’s Framework,” <i>ACM Transactions on Computational Logic</i>,
    vol. 24, no. 3, pp. 1–25, 2023, doi: <a href="https://doi.org/10.1145/3582499">10.1145/3582499</a>.'
  mla: Mahmood, Yasir, et al. “Parameterized Complexity of Logic-Based Argumentation
    in Schaefer’s Framework.” <i>ACM Transactions on Computational Logic</i>, vol.
    24, no. 3, Association for Computing Machinery (ACM), 2023, pp. 1–25, doi:<a href="https://doi.org/10.1145/3582499">10.1145/3582499</a>.
  short: Y. Mahmood, A. Meier, J. Schmidt, ACM Transactions on Computational Logic
    24 (2023) 1–25.
date_created: 2024-06-04T09:58:17Z
date_updated: 2024-06-04T15:52:54Z
department:
- _id: '574'
doi: 10.1145/3582499
intvolume: '        24'
issue: '3'
language:
- iso: eng
page: 1-25
publication: ACM Transactions on Computational Logic
publication_identifier:
  issn:
  - 1529-3785
  - 1557-945X
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework
type: journal_article
user_id: '99353'
volume: 24
year: '2023'
...