Email this article 
ELEMENTARY INVARIANTS FOR QUANTIFIED PROBABILITY LOGIC
- Authors: Speranski S.O.1
-
Affiliations:
- Steklov Mathematical Institute of Russian Academy of Sciences
- Issue: Vol 510, No 1 (2023)
- Pages: 8-12
- Section: MATHEMATICS
- URL: https://journals.rcsi.science/2686-9543/article/view/134353
- DOI: https://doi.org/10.31857/S2686954323600040
- EDN: https://elibrary.ru/XHTJMV
- ID: 134353
Cite item
Open Access
Access granted
Subscription Access
Abstract
Let QPL be the two-sorted probabilistic language proposed in [8], which expands the well-known ‘polynomial’ language described in [3, Section 6] by adding quantifiers over events. We show that all atomless spaces have the same QPL-theory, and this theory is decidable. Also we introduce the notion of elementary invariant for QPL and use it for obtaining exact complexity upper bounds for some interesting probabilistic theories.
About the authors
S. O. Speranski
Steklov Mathematical Institute of Russian Academy of Sciences
Author for correspondence.
Email: katze.tail@gmail.com
Russian Federation, Moscow
References
- Abadi M., Halpern J.Y. Decidability and expressiveness for first-order logics of probability // Information and Computation. 1994. V. 112. № 1. P. 1–36.
- Ershov Yu.L., Lavrov I.A., Taimanov A.D., Taitslin M.A. Elementary theories // Russian Mathematical Surveys. 1965. V. 20. № 4. P 35–105.
- Fagin R., Halpern J.Y., Megiddo N. A logic for reasoning about probabilities // Information and Computation. 1990. V. 87. № 1–2. P. 78–128.
- Halpern J.Y. An analysis of first-order logics of probability // Artificial Intelligence. 1990. V. 46. № 3. P. 311–350.
- Halpern J.Y. Presburger arithmetic with unary predicates is complete // Journal of Symbolic Logic. 1991. V. 56. № 2. P. 637–642.
- Koppelberg S. General theory of Boolean algebras // in Handbook of Boolean Algebras, Vol. 1, Ed. by Monk J.D., Bonnet R. (North-Holland, 1989), P. 1–311.
- Solovay R.M., Arthan R.D., Harrison J. Some new results on decidability for elementary algebra and geometry // Annals of Pure and Applied Logic. 2012. V. 163. № 12. P. 1765–1802.
- Speranski S.O. Quantifying over events in probability logic: an introduction // Mathematical Structures in Computer Science. 2017. V. 27. № 8. P. 1581–1600.
- Speranski S.O. A note on definability in fragments of arithmetic with free unary predicates // Archive for Mathematical Logic. 2013. V. 52. № 5–6. P. 507–516.
- Speranski S.O. Complexity for probability logic with quantifiers over propositions // Journal of Logic and Computation. 2013. V. 23. № 5. P. 1035–1055.
- Speranski S.O. Quantification over propositional formulas in probability logic: decidability issues // Algebra and Logic. 2011. V. 50. № 4. P. 365–374.
- Tarski A. A Decision Method for Elementary Algebra and Geometry (University of California Press, 1951).
Supplementary files
