- PII
- 10.31857/S2686954323600040-1
- DOI
- 10.31857/S2686954323600040
- Publication type
- Status
- Published
- Authors
- Volume/ Edition
- Volume 510 / Issue number 1
- Pages
- 8-12
- 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.
- Keywords
- вероятностная логика квантификация по событиям элементарные инварианты сложность
- Date of publication
- 17.09.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 12
References
- 1. Abadi M., Halpern J.Y. Decidability and expressiveness for first-order logics of probability // Information and Computation. 1994. V. 112. № 1. P. 1–36.
- 2. Ershov Yu.L., Lavrov I.A., Taimanov A.D., Taitslin M.A. Elementary theories // Russian Mathematical Surveys. 1965. V. 20. № 4. P 35–105.
- 3. Fagin R., Halpern J.Y., Megiddo N. A logic for reasoning about probabilities // Information and Computation. 1990. V. 87. № 1–2. P. 78–128.
- 4. Halpern J.Y. An analysis of first-order logics of probability // Artificial Intelligence. 1990. V. 46. № 3. P. 311–350.
- 5. Halpern J.Y. Presburger arithmetic with unary predicates is complete // Journal of Symbolic Logic. 1991. V. 56. № 2. P. 637–642.
- 6. 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.
- 7. 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.
- 8. Speranski S.O. Quantifying over events in probability logic: an introduction // Mathematical Structures in Computer Science. 2017. V. 27. № 8. P. 1581–1600.
- 9. 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.
- 10. Speranski S.O. Complexity for probability logic with quantifiers over propositions // Journal of Logic and Computation. 2013. V. 23. № 5. P. 1035–1055.
- 11. Speranski S.O. Quantification over propositional formulas in probability logic: decidability issues // Algebra and Logic. 2011. V. 50. № 4. P. 365–374.
- 12. Tarski A. A Decision Method for Elementary Algebra and Geometry (University of California Press, 1951).
