Details
| Original language | English |
|---|---|
| Article number | 3 |
| Journal | Journal of Logic and Computation |
| Volume | 35 |
| Issue number | 3 |
| Publication status | Published - 30 Mar 2025 |
Abstract
Keywords
- probabilistic team semantics, model checking, satisfiability, validity, computational complexity, expressivity of logics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Journal of Logic and Computation, Vol. 35, No. 3, 3, 30.03.2025.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Logics with probabilistic team semantics and the Boolean negation.
AU - Hannula, Miika
AU - Hirvonen, Minna
AU - Kontinen, Juha
AU - Mahmood, Yasir
AU - Meier, Arne
AU - Virtema, Jonni
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2025/3/30
Y1 - 2025/3/30
N2 - 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.
AB - 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.
KW - probabilistic team semantics
KW - model checking
KW - satisfiability
KW - validity
KW - computational complexity
KW - expressivity of logics
U2 - 10.1093/logcom/exaf021
DO - 10.1093/logcom/exaf021
M3 - Article
VL - 35
JO - Journal of Logic and Computation
JF - Journal of Logic and Computation
SN - 0955-792X
IS - 3
M1 - 3
ER -