Details
| Original language | English |
|---|---|
| Title of host publication | JELIA 2023 |
| Subtitle of host publication | Logics in Artificial Intelligence |
| Editors | Sarah Gaggl, Maria Vanina Martinez, Magdalena Ortiz, Magdalena Ortiz |
| Place of Publication | Cham |
| Pages | 665-680 |
| Number of pages | 16 |
| ISBN (electronic) | 978-3-031-43619-2 |
| Publication status | Published - 2023 |
| Event | JELIA 2023 - 18th Edition of the European Conference on Logics in Artificial Intelligence - Dresden, Germany Duration: 20 Sept 2023 → 22 Sept 2023 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 14281 LNAI |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
Abstract
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 FOPT. We give a comprehensive picture of the relative expressivity of these logics together 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.
Keywords
- Computational Complexity, Expressivity of Logics, Model Checking, Probabilistic Team Semantics, Satisfiability, Validity
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- General Computer Science
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
JELIA 2023: Logics in Artificial Intelligence. ed. / Sarah Gaggl; Maria Vanina Martinez; Magdalena Ortiz; Magdalena Ortiz. Cham, 2023. p. 665-680 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14281 LNAI).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
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 - The first author is supported by the ERC grant 101020762. The second author is supported by Academy of Finland grant 345634. The third author is supported by Academy of Finland grants 338259 and 345634. The fourth author appreciates funding by the European Union’s Horizon Europe research and innovation programme within project ENEXA (101070305). The fifth author appreciates funding by the German Research Foundation (DFG), project ME 4279/3-1. The sixth author is partially funded by the German Research Foundation (DFG), project VI 1045/1-1.
PY - 2023
Y1 - 2023
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 FOPT. We give a comprehensive picture of the relative expressivity of these logics together 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 FOPT. We give a comprehensive picture of the relative expressivity of these logics together 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 - Computational Complexity
KW - Expressivity of Logics
KW - Model Checking
KW - Probabilistic Team Semantics
KW - Satisfiability
KW - Validity
UR - http://www.scopus.com/inward/record.url?scp=85174510081&partnerID=8YFLogxK
U2 - 10.48550/arXiv.2306.00420
DO - 10.48550/arXiv.2306.00420
M3 - Conference contribution
SN - 978-3-031-43618-5
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 665
EP - 680
BT - JELIA 2023
A2 - Gaggl, Sarah
A2 - Martinez, Maria Vanina
A2 - Ortiz, Magdalena
A2 - Ortiz, Magdalena
CY - Cham
T2 - JELIA 2023 - 18th Edition of the European Conference on Logics in Artificial Intelligence
Y2 - 20 September 2023 through 22 September 2023
ER -