---
_id: '61065'
abstract:
- lang: eng
  text: Abduction is the task of computing a sufficient extension of a knowledge base
    (KB) that entails a conclusion not entailed by the original KB. It serves to compute
    explanations, or hypotheses, for such missing entailments. While this task has
    been intensively investigated for perfect data and under classical semantics,
    less is known about abduction when erroneous data results in inconsistent KBs.
    In this paper we define a suitable notion of abduction under repair semantics
    and propose a set of minimality criteria that guides abduction towards `useful'
    hypotheses. We provide initial complexity results on deciding existence of and
    verifying abductive solutions with these criteria, under different repair semantics
    and for the description logics DL-Lite and EL_bot.
author:
- first_name: Anselm
  full_name: Haak, Anselm
  id: '109969'
  last_name: Haak
- first_name: Patrick
  full_name: Koopmann, Patrick
  last_name: Koopmann
- first_name: Yasir
  full_name: Mahmood, Yasir
  id: '99353'
  last_name: Mahmood
- first_name: Anni-Yasmin
  full_name: Turhan, Anni-Yasmin
  id: '104470'
  last_name: Turhan
citation:
  ama: Haak A, Koopmann P, Mahmood Y, Turhan A-Y. Why not? Developing ABox Abduction
    beyond Repairs. <i>arXiv:250721955</i>. Published online 2025.
  apa: Haak, A., Koopmann, P., Mahmood, Y., &#38; Turhan, A.-Y. (2025). Why not? Developing
    ABox Abduction beyond Repairs. In <i>arXiv:2507.21955</i>.
  bibtex: '@article{Haak_Koopmann_Mahmood_Turhan_2025, title={Why not? Developing
    ABox Abduction beyond Repairs}, journal={arXiv:2507.21955}, author={Haak, Anselm
    and Koopmann, Patrick and Mahmood, Yasir and Turhan, Anni-Yasmin}, year={2025}
    }'
  chicago: Haak, Anselm, Patrick Koopmann, Yasir Mahmood, and Anni-Yasmin Turhan.
    “Why Not? Developing ABox Abduction beyond Repairs.” <i>ArXiv:2507.21955</i>,
    2025.
  ieee: A. Haak, P. Koopmann, Y. Mahmood, and A.-Y. Turhan, “Why not? Developing ABox
    Abduction beyond Repairs,” <i>arXiv:2507.21955</i>. 2025.
  mla: Haak, Anselm, et al. “Why Not? Developing ABox Abduction beyond Repairs.” <i>ArXiv:2507.21955</i>,
    2025.
  short: A. Haak, P. Koopmann, Y. Mahmood, A.-Y. Turhan, ArXiv:2507.21955 (2025).
date_created: 2025-08-29T07:58:08Z
date_updated: 2026-02-05T13:55:48Z
department:
- _id: '574'
- _id: '888'
external_id:
  arxiv:
  - '2507.21955'
language:
- iso: eng
project:
- _id: '121'
  name: 'TRR 318; TP B01: Ein dialogbasierter Ansatz zur Erklärung von Modellen des
    maschinellen Lernens'
publication: arXiv:2507.21955
status: public
title: Why not? Developing ABox Abduction beyond Repairs
type: preprint
user_id: '109969'
year: '2025'
...
---
_id: '63888'
author:
- first_name: Anselm
  full_name: Haak, Anselm
  id: '109969'
  last_name: Haak
- first_name: Patrick
  full_name: Koopmann, Patrick
  last_name: Koopmann
- first_name: Yasir
  full_name: Mahmood, Yasir
  id: '99353'
  last_name: Mahmood
- first_name: Anni-Yasmin
  full_name: Turhan, Anni-Yasmin
  id: '104470'
  last_name: Turhan
citation:
  ama: 'Haak A, Koopmann P, Mahmood Y, Turhan A-Y. Why not? Developing ABox Abduction
    beyond Repairs. In: Tendera L, Ibanez Garcia Y, Koopmann P, eds. <i>Proceedings
    of the 38th International Workshop on Description Logics - DL 2025</i>. ; 2025.'
  apa: Haak, A., Koopmann, P., Mahmood, Y., &#38; Turhan, A.-Y. (2025). Why not? Developing
    ABox Abduction beyond Repairs. In L. Tendera, Y. Ibanez Garcia, &#38; P. Koopmann
    (Eds.), <i>Proceedings of the 38th International Workshop on Description Logics
    - DL 2025</i>.
  bibtex: '@inproceedings{Haak_Koopmann_Mahmood_Turhan_2025, title={Why not? Developing
    ABox Abduction beyond Repairs}, booktitle={Proceedings of the 38th International
    Workshop on Description Logics - DL 2025}, author={Haak, Anselm and Koopmann,
    Patrick and Mahmood, Yasir and Turhan, Anni-Yasmin}, editor={Tendera, Lidia and
    Ibanez Garcia, Yazmin and Koopmann, Patrick}, year={2025} }'
  chicago: Haak, Anselm, Patrick Koopmann, Yasir Mahmood, and Anni-Yasmin Turhan.
    “Why Not? Developing ABox Abduction beyond Repairs.” In <i>Proceedings of the
    38th International Workshop on Description Logics - DL 2025</i>, edited by Lidia
    Tendera, Yazmin Ibanez Garcia, and Patrick Koopmann, 2025.
  ieee: A. Haak, P. Koopmann, Y. Mahmood, and A.-Y. Turhan, “Why not? Developing ABox
    Abduction beyond Repairs,” in <i>Proceedings of the 38th International Workshop
    on Description Logics - DL 2025</i>, Opole, Poland, 2025.
  mla: Haak, Anselm, et al. “Why Not? Developing ABox Abduction beyond Repairs.” <i>Proceedings
    of the 38th International Workshop on Description Logics - DL 2025</i>, edited
    by Lidia Tendera et al., 2025.
  short: 'A. Haak, P. Koopmann, Y. Mahmood, A.-Y. Turhan, in: L. Tendera, Y. Ibanez
    Garcia, P. Koopmann (Eds.), Proceedings of the 38th International Workshop on
    Description Logics - DL 2025, 2025.'
conference:
  end_date: 2025-09-06
  location: Opole, Poland
  name: Description Logics 2025
  start_date: 2025-09-03
date_created: 2026-02-05T13:54:08Z
date_updated: 2026-02-05T13:55:27Z
department:
- _id: '888'
- _id: '574'
editor:
- first_name: Lidia
  full_name: Tendera, Lidia
  last_name: Tendera
- first_name: Yazmin
  full_name: Ibanez Garcia, Yazmin
  last_name: Ibanez Garcia
- first_name: Patrick
  full_name: Koopmann, Patrick
  last_name: Koopmann
language:
- iso: eng
main_file_link:
- url: https://ceur-ws.org/Vol-4091/paper25.pdf
publication: Proceedings of the 38th International Workshop on Description Logics
  - DL 2025
status: public
title: Why not? Developing ABox Abduction beyond Repairs
type: conference
user_id: '109969'
year: '2025'
...
---
_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: '60168'
author:
- first_name: Holger
  full_name: Dell, Holger
  last_name: Dell
- first_name: Anselm
  full_name: Haak, Anselm
  id: '109969'
  last_name: Haak
- first_name: Melvin
  full_name: Kallmayer, Melvin
  last_name: Kallmayer
- first_name: Leo
  full_name: Wennmann, Leo
  last_name: Wennmann
citation:
  ama: 'Dell H, Haak A, Kallmayer M, Wennmann L. Solving Polynomial Equations Over
    Finite Fields. In: <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete
    Algorithms (SODA)</i>. Society for Industrial and Applied Mathematics; 2025. doi:<a
    href="https://doi.org/10.1137/1.9781611978322.90">10.1137/1.9781611978322.90</a>'
  apa: Dell, H., Haak, A., Kallmayer, M., &#38; Wennmann, L. (2025). Solving Polynomial
    Equations Over Finite Fields. <i>Proceedings of the 2025 Annual ACM-SIAM Symposium
    on Discrete Algorithms (SODA)</i>. ACM-SIAM Symposium on Discrete Algorithms (SODA25),
    New Orleans, Louisiana, U.S. <a href="https://doi.org/10.1137/1.9781611978322.90">https://doi.org/10.1137/1.9781611978322.90</a>
  bibtex: '@inproceedings{Dell_Haak_Kallmayer_Wennmann_2025, place={Philadelphia,
    PA}, title={Solving Polynomial Equations Over Finite Fields}, DOI={<a href="https://doi.org/10.1137/1.9781611978322.90">10.1137/1.9781611978322.90</a>},
    booktitle={Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms
    (SODA)}, publisher={Society for Industrial and Applied Mathematics}, author={Dell,
    Holger and Haak, Anselm and Kallmayer, Melvin and Wennmann, Leo}, year={2025}
    }'
  chicago: 'Dell, Holger, Anselm Haak, Melvin Kallmayer, and Leo Wennmann. “Solving
    Polynomial Equations Over Finite Fields.” In <i>Proceedings of the 2025 Annual
    ACM-SIAM Symposium on Discrete Algorithms (SODA)</i>. Philadelphia, PA: Society
    for Industrial and Applied Mathematics, 2025. <a href="https://doi.org/10.1137/1.9781611978322.90">https://doi.org/10.1137/1.9781611978322.90</a>.'
  ieee: 'H. Dell, A. Haak, M. Kallmayer, and L. Wennmann, “Solving Polynomial Equations
    Over Finite Fields,” presented at the ACM-SIAM Symposium on Discrete Algorithms
    (SODA25), New Orleans, Louisiana, U.S., 2025, doi: <a href="https://doi.org/10.1137/1.9781611978322.90">10.1137/1.9781611978322.90</a>.'
  mla: Dell, Holger, et al. “Solving Polynomial Equations Over Finite Fields.” <i>Proceedings
    of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i>, Society
    for Industrial and Applied Mathematics, 2025, doi:<a href="https://doi.org/10.1137/1.9781611978322.90">10.1137/1.9781611978322.90</a>.
  short: 'H. Dell, A. Haak, M. Kallmayer, L. Wennmann, in: Proceedings of the 2025
    Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial
    and Applied Mathematics, Philadelphia, PA, 2025.'
conference:
  end_date: 2025-01-15
  location: New Orleans, Louisiana, U.S.
  name: ACM-SIAM Symposium on Discrete Algorithms (SODA25)
  start_date: 2025-01-12
date_created: 2025-06-10T13:48:14Z
date_updated: 2026-04-14T08:18:11Z
doi: 10.1137/1.9781611978322.90
language:
- iso: eng
place: Philadelphia, PA
publication: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms
  (SODA)
publication_identifier:
  isbn:
  - '9781611978322'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
status: public
title: Solving Polynomial Equations Over Finite Fields
type: conference
user_id: '109969'
year: '2025'
...