---
_id: '59912'
abstract:
- lang: eng
  text: "<jats:title>Abstract</jats:title>\r\n               <jats:p>We study the
    expressivity and the complexity of various logics in probabilistic team semantics
    with the Boolean negation. In particular, we study the extension of probabilistic
    independence logic with the Boolean negation, and a recently introduced logic
    first-order theory of random variables with probabilistic independence. We give
    several results that compare the expressivity of these logics with the most studied
    logics in probabilistic team semantics setting, as well as relating their expressivity
    to a numerical variant of second-order logic. In addition, we introduce novel
    entropy atoms and show that the extension of first-order logic by entropy atoms
    subsumes probabilistic independence logic. Finally, we obtain some results on
    the complexity of model checking, validity and satisfiability of our logics.</jats:p>"
author:
- first_name: Miika
  full_name: Hannula, Miika
  last_name: Hannula
- first_name: Minna
  full_name: Hirvonen, Minna
  last_name: Hirvonen
- 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: Jonni
  full_name: Virtema, Jonni
  last_name: Virtema
citation:
  ama: Hannula M, Hirvonen M, Kontinen J, Mahmood Y, Meier A, Virtema J. Logics with
    probabilistic team semantics and the Boolean negation. <i>Journal of Logic and
    Computation</i>. 2025;35(3). doi:<a href="https://doi.org/10.1093/logcom/exaf021">10.1093/logcom/exaf021</a>
  apa: Hannula, M., Hirvonen, M., Kontinen, J., Mahmood, Y., Meier, A., &#38; Virtema,
    J. (2025). Logics with probabilistic team semantics and the Boolean negation.
    <i>Journal of Logic and Computation</i>, <i>35</i>(3). <a href="https://doi.org/10.1093/logcom/exaf021">https://doi.org/10.1093/logcom/exaf021</a>
  bibtex: '@article{Hannula_Hirvonen_Kontinen_Mahmood_Meier_Virtema_2025, title={Logics
    with probabilistic team semantics and the Boolean negation}, volume={35}, DOI={<a
    href="https://doi.org/10.1093/logcom/exaf021">10.1093/logcom/exaf021</a>}, number={3},
    journal={Journal of Logic and Computation}, publisher={Oxford University Press
    (OUP)}, author={Hannula, Miika and Hirvonen, Minna and Kontinen, Juha and Mahmood,
    Yasir and Meier, Arne and Virtema, Jonni}, year={2025} }'
  chicago: Hannula, Miika, Minna Hirvonen, Juha Kontinen, Yasir Mahmood, Arne Meier,
    and Jonni Virtema. “Logics with Probabilistic Team Semantics and the Boolean Negation.”
    <i>Journal of Logic and Computation</i> 35, no. 3 (2025). <a href="https://doi.org/10.1093/logcom/exaf021">https://doi.org/10.1093/logcom/exaf021</a>.
  ieee: 'M. Hannula, M. Hirvonen, J. Kontinen, Y. Mahmood, A. Meier, and J. Virtema,
    “Logics with probabilistic team semantics and the Boolean negation,” <i>Journal
    of Logic and Computation</i>, vol. 35, no. 3, 2025, doi: <a href="https://doi.org/10.1093/logcom/exaf021">10.1093/logcom/exaf021</a>.'
  mla: Hannula, Miika, et al. “Logics with Probabilistic Team Semantics and the Boolean
    Negation.” <i>Journal of Logic and Computation</i>, vol. 35, no. 3, Oxford University
    Press (OUP), 2025, doi:<a href="https://doi.org/10.1093/logcom/exaf021">10.1093/logcom/exaf021</a>.
  short: M. Hannula, M. Hirvonen, J. Kontinen, Y. Mahmood, A. Meier, J. Virtema, Journal
    of Logic and Computation 35 (2025).
date_created: 2025-05-15T11:07:28Z
date_updated: 2025-09-11T10:00:26Z
department:
- _id: '574'
doi: 10.1093/logcom/exaf021
intvolume: '        35'
issue: '3'
language:
- iso: eng
project:
- _id: '121'
  name: 'TRR 318; TP B01: Ein dialogbasierter Ansatz zur Erklärung von Modellen des
    maschinellen Lernens'
publication: Journal of Logic and Computation
publication_identifier:
  issn:
  - 0955-792X
  - 1465-363X
publication_status: published
publisher: Oxford University Press (OUP)
status: public
title: Logics with probabilistic team semantics and the Boolean negation
type: journal_article
user_id: '99353'
volume: 35
year: '2025'
...
---
_id: '45847'
abstract:
- lang: eng
  text: "<jats:title>Abstract</jats:title>\r\n               <jats:p>In this paper,
    we investigate the parameterized complexity of model checking for Dependence and
    Independence logic, which are well studied logics in the area of Team Semantics.
    We start with a list of nine immediate parameterizations for this problem, namely
    the number of disjunctions (i.e. splits)/(free) variables/universal quantifiers,
    formula-size, the tree-width of the Gaifman graph of the input structure, the
    size of the universe/team and the arity of dependence atoms. We present a comprehensive
    picture of the parameterized complexity of model checking and obtain a division
    of the problem into tractable and various intractable degrees. Furthermore, we
    also consider the complexity of the most important variants (data and expression
    complexity) of the model checking problem by fixing parts of the input.</jats:p>"
author:
- first_name: Juha
  full_name: Kontinen, Juha
  last_name: Kontinen
- first_name: Arne
  full_name: Meier, Arne
  last_name: Meier
- first_name: Yasir
  full_name: Mahmood, Yasir
  id: '99353'
  last_name: Mahmood
citation:
  ama: Kontinen J, Meier A, Mahmood Y. A parameterized view on the complexity of dependence
    and independence logic. <i>Journal of Logic and Computation</i>. 2022;32(8):1624-1644.
    doi:<a href="https://doi.org/10.1093/logcom/exac070">10.1093/logcom/exac070</a>
  apa: Kontinen, J., Meier, A., &#38; Mahmood, Y. (2022). A parameterized view on
    the complexity of dependence and independence logic. <i>Journal of Logic and Computation</i>,
    <i>32</i>(8), 1624–1644. <a href="https://doi.org/10.1093/logcom/exac070">https://doi.org/10.1093/logcom/exac070</a>
  bibtex: '@article{Kontinen_Meier_Mahmood_2022, title={A parameterized view on the
    complexity of dependence and independence logic}, volume={32}, DOI={<a href="https://doi.org/10.1093/logcom/exac070">10.1093/logcom/exac070</a>},
    number={8}, journal={Journal of Logic and Computation}, publisher={Oxford University
    Press (OUP)}, author={Kontinen, Juha and Meier, Arne and Mahmood, Yasir}, year={2022},
    pages={1624–1644} }'
  chicago: 'Kontinen, Juha, Arne Meier, and Yasir Mahmood. “A Parameterized View on
    the Complexity of Dependence and Independence Logic.” <i>Journal of Logic and
    Computation</i> 32, no. 8 (2022): 1624–44. <a href="https://doi.org/10.1093/logcom/exac070">https://doi.org/10.1093/logcom/exac070</a>.'
  ieee: 'J. Kontinen, A. Meier, and Y. Mahmood, “A parameterized view on the complexity
    of dependence and independence logic,” <i>Journal of Logic and Computation</i>,
    vol. 32, no. 8, pp. 1624–1644, 2022, doi: <a href="https://doi.org/10.1093/logcom/exac070">10.1093/logcom/exac070</a>.'
  mla: Kontinen, Juha, et al. “A Parameterized View on the Complexity of Dependence
    and Independence Logic.” <i>Journal of Logic and Computation</i>, vol. 32, no.
    8, Oxford University Press (OUP), 2022, pp. 1624–44, doi:<a href="https://doi.org/10.1093/logcom/exac070">10.1093/logcom/exac070</a>.
  short: J. Kontinen, A. Meier, Y. Mahmood, Journal of Logic and Computation 32 (2022)
    1624–1644.
date_created: 2023-07-03T11:36:55Z
date_updated: 2024-06-04T16:06:37Z
doi: 10.1093/logcom/exac070
extern: '1'
intvolume: '        32'
issue: '8'
keyword:
- Logic
- Hardware and Architecture
- Arts and Humanities (miscellaneous)
- Software
- Theoretical Computer Science
language:
- iso: eng
page: 1624-1644
publication: Journal of Logic and Computation
publication_identifier:
  issn:
  - 0955-792X
  - 1465-363X
publication_status: published
publisher: Oxford University Press (OUP)
status: public
title: A parameterized view on the complexity of dependence and independence logic
type: journal_article
user_id: '99353'
volume: 32
year: '2022'
...
---
_id: '45844'
abstract:
- lang: eng
  text: "<jats:title>Abstract</jats:title>\r\n               <jats:p>Abductive reasoning
    is a non-monotonic formalism stemming from the work of Peirce. It describes the
    process of deriving the most plausible explanations of known facts. Considering
    the positive version, asking for sets of variables as explanations, we study,
    besides the problem of wether there exists a set of explanations, two explanation
    size limited variants of this reasoning problem (less than or equal to, and equal
    to a given size bound). In this paper, we present a thorough two-dimensional classification
    of these problems: the first dimension is regarding the parameterized complexity
    under a wealth of different parameterizations, and the second dimension spans
    through all possible Boolean fragments of these problems in Schaefer’s constraint
    satisfaction framework with co-clones (T. J. Schaefer. The complexity of satisfiability
    problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing,
    May 1–3, 1978, San Diego, California, USA, R.J. Lipton, W.A. Burkhard, W.J. Savitch,
    E.P. Friedman, A.V. Aho eds, pp. 216–226. ACM, 1978). Thereby, we almost complete
    the parameterized complexity classification program initiated by Fellows et al.
    (The parameterized complexity of abduction. In Proceedings of the Twenty-Sixth
    AAAI Conference on Articial Intelligence, July 22–26, 2012, Toronto, Ontario,
    Canada, J. Homann, B. Selman eds. AAAI Press, 2012), partially building on the
    results by Nordh and Zanuttini (What makes propositional abduction tractable.
    Artificial Intelligence, 172, 1245–1284, 2008). In this process, we outline a
    fine-grained analysis of the inherent parameterized intractability of these problems
    and pinpoint their FPT parts. As the standard algebraic approach is not applicable
    to our problems, we develop an alternative method that makes the algebraic tools
    partially available again.</jats:p>"
author:
- first_name: Yasir
  full_name: Mahmood, Yasir
  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 abduction in Schaefer’s
    framework. <i>Journal of Logic and Computation</i>. 2021;31(1):266-296. doi:<a
    href="https://doi.org/10.1093/logcom/exaa079">10.1093/logcom/exaa079</a>
  apa: Mahmood, Y., Meier, A., &#38; Schmidt, J. (2021). Parameterized complexity
    of abduction in Schaefer’s framework. <i>Journal of Logic and Computation</i>,
    <i>31</i>(1), 266–296. <a href="https://doi.org/10.1093/logcom/exaa079">https://doi.org/10.1093/logcom/exaa079</a>
  bibtex: '@article{Mahmood_Meier_Schmidt_2021, title={Parameterized complexity of
    abduction in Schaefer’s framework}, volume={31}, DOI={<a href="https://doi.org/10.1093/logcom/exaa079">10.1093/logcom/exaa079</a>},
    number={1}, journal={Journal of Logic and Computation}, publisher={Oxford University
    Press (OUP)}, author={Mahmood, Yasir and Meier, Arne and Schmidt, Johannes}, year={2021},
    pages={266–296} }'
  chicago: 'Mahmood, Yasir, Arne Meier, and Johannes Schmidt. “Parameterized Complexity
    of Abduction in Schaefer’s Framework.” <i>Journal of Logic and Computation</i>
    31, no. 1 (2021): 266–96. <a href="https://doi.org/10.1093/logcom/exaa079">https://doi.org/10.1093/logcom/exaa079</a>.'
  ieee: 'Y. Mahmood, A. Meier, and J. Schmidt, “Parameterized complexity of abduction
    in Schaefer’s framework,” <i>Journal of Logic and Computation</i>, vol. 31, no.
    1, pp. 266–296, 2021, doi: <a href="https://doi.org/10.1093/logcom/exaa079">10.1093/logcom/exaa079</a>.'
  mla: Mahmood, Yasir, et al. “Parameterized Complexity of Abduction in Schaefer’s
    Framework.” <i>Journal of Logic and Computation</i>, vol. 31, no. 1, Oxford University
    Press (OUP), 2021, pp. 266–96, doi:<a href="https://doi.org/10.1093/logcom/exaa079">10.1093/logcom/exaa079</a>.
  short: Y. Mahmood, A. Meier, J. Schmidt, Journal of Logic and Computation 31 (2021)
    266–296.
date_created: 2023-07-03T11:35:23Z
date_updated: 2024-06-04T16:03:14Z
department:
- _id: '574'
doi: 10.1093/logcom/exaa079
extern: '1'
intvolume: '        31'
issue: '1'
keyword:
- Logic
- Hardware and Architecture
- Arts and Humanities (miscellaneous)
- Software
- Theoretical Computer Science
language:
- iso: eng
page: 266-296
publication: Journal of Logic and Computation
publication_identifier:
  issn:
  - 0955-792X
  - 1465-363X
publication_status: published
publisher: Oxford University Press (OUP)
status: public
title: Parameterized complexity of abduction in Schaefer’s framework
type: journal_article
user_id: '99353'
volume: 31
year: '2021'
...