On the decision problem for quantified probability logics
- Authors: Speranski S.O.1
-
Affiliations:
- Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia
- Issue: Vol 89, No 3 (2025)
- Pages: 193-211
- Section: Articles
- URL: https://bakhtiniada.ru/1607-0046/article/view/303962
- DOI: https://doi.org/10.4213/im9652
- ID: 303962
Cite item
Open Access
Access granted
Subscription Access
Abstract
Let $\mathsf{QPL}^{\mathrm{e}}$ expand the quantifier-free “polynomial” probability logic of [4](R. Fagin et al., 1990)by adding quantifiers over arbitrary events; it can be viewed as a one-sorted elementary language for reasoning about probability spaces. We prove that the $\Sigma_2$-fragment of the $\mathsf{QPL}^{\mathrm{e}}$-theory of finite spaces is hereditarily undecidable. By earlier observations, this implies that $\Pi_2$ is the maximal decidable prefix fragment of $\mathsf{QPL}^{\mathrm{e}}$. Moreover, we obtain similar results for two natural one-sorted logics of probability that emerge from [1](M. Abadi and J. Y. Halpern, 1994).
About the authors
Stanislav Olegovich Speranski
Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia
Author for correspondence.
Email: katze.tail@gmail.com
Candidate of physico-mathematical sciences, no status
References
- M. Abadi, J. Y. Halpern, “Decidability and expressiveness for first-order logics of probability”, Inform. and Comput., 112:1 (1994), 1–36
- E. Börger, E. Grädel, Y. Gurevich, The classical decision problem, Perspect. Math. Logic, Springer-Verlag, Berlin, 1997, xii+482 pp.
- Ю. Л. Ершов, И. А. Лавров, А. Д. Тайманов, М. А. Тайцлин, “Элементарные теории”, УМН, 20:4(124) (1965), 37–108
- R. Fagin, J. Y. Halpern, N. Megiddo, “A logic for reasoning about probabilities”, Inform. and Comput., 87:1-2 (1990), 78–128
- J. Y. Halpern, “An analysis of first-order logics of probability”, Artificial Intelligence, 46:3 (1990), 311–350
- D. Ibeling, T. Icard, K. Mierzewski, M. Mosse, “Probing the quantitative–qualitative divide in probabilistic reasoning”, Ann. Pure Appl. Logic, 175:9 (2024), 103339, 45 pp.
- A. Nies, “Undecidable fragments of elementary theories”, Algebra Universalis, 35:1 (1996), 8–33
- A. Perovic, Z. Ognjanovic, M. Raškovic, Z. Markovic, “A probabilistic logic with polynomial weight formulas”, Foundations of information and knowledge systems (Pisa, 2008), Lecture Notes in Comput. Sci., 4932, Springer, Berlin, 2008, 239–252
- Z. Ognjanovic, M. Raškovic, Z. Markovic, Probability logics. Probability-based formalization of uncertain reasoning, Springer, Cham, 2016, xi+215 pp.
- R. M. Solovay, R. D. Arthan, J. Harrison, “Some new results on decidability for elementary algebra and geometry”, Ann. Pure Appl. Logic, 163:12 (2012), 1765–1802
- С. О. Сперанский, “Квантификация по пропозициональным формулам в вероятностной логике: вопросы разрешимости”, Алгебра и логика, 50:4 (2011), 533–546
- S. O. Speranski, “A note on hereditarily $Pi^0_1$- and $Sigma^0_1$-complete sets of sentences”, J. Logic Comput., 26:5 (2016), 1729–1741
- S. O. Speranski, “Quantifying over events in probability logic: an introduction”, Math. Structures Comput. Sci., 27:8 (2017), 1581–1600
- S. O. Speranski, “An ‘elementary’ perspective on reasoning about probability spaces”, Log. J. IGPL, 2024, jzae042, Publ. online
- S. O. Speranski, “Sharpening complexity results in quantified probability logic”, Log. J. IGPL, 2024, jzae114, Publ. online
- A. Tarski, A decision method for elementary algebra and geometry, 2nd ed., Univ. of California Press, Berkeley–Los Angeles, CA, 1951, iii+63 pp.
Supplementary files
