@article{59912,
  abstract     = {{<jats:title>Abstract</jats:title>
               <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       = {{Hannula, Miika and Hirvonen, Minna and Kontinen, Juha and Mahmood, Yasir and Meier, Arne and Virtema, Jonni}},
  issn         = {{0955-792X}},
  journal      = {{Journal of Logic and Computation}},
  number       = {{3}},
  publisher    = {{Oxford University Press (OUP)}},
  title        = {{{Logics with probabilistic team semantics and the Boolean negation}}},
  doi          = {{10.1093/logcom/exaf021}},
  volume       = {{35}},
  year         = {{2025}},
}

@article{45847,
  abstract     = {{<jats:title>Abstract</jats:title>
               <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       = {{Kontinen, Juha and Meier, Arne and Mahmood, Yasir}},
  issn         = {{0955-792X}},
  journal      = {{Journal of Logic and Computation}},
  keywords     = {{Logic, Hardware and Architecture, Arts and Humanities (miscellaneous), Software, Theoretical Computer Science}},
  number       = {{8}},
  pages        = {{1624--1644}},
  publisher    = {{Oxford University Press (OUP)}},
  title        = {{{A parameterized view on the complexity of dependence and independence logic}}},
  doi          = {{10.1093/logcom/exac070}},
  volume       = {{32}},
  year         = {{2022}},
}

@article{45844,
  abstract     = {{<jats:title>Abstract</jats:title>
               <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       = {{Mahmood, Yasir and Meier, Arne and Schmidt, Johannes}},
  issn         = {{0955-792X}},
  journal      = {{Journal of Logic and Computation}},
  keywords     = {{Logic, Hardware and Architecture, Arts and Humanities (miscellaneous), Software, Theoretical Computer Science}},
  number       = {{1}},
  pages        = {{266--296}},
  publisher    = {{Oxford University Press (OUP)}},
  title        = {{{Parameterized complexity of abduction in Schaefer’s framework}}},
  doi          = {{10.1093/logcom/exaa079}},
  volume       = {{31}},
  year         = {{2021}},
}