电邮这篇文章 ELEMENTARY INVARIANTS FOR QUANTIFIED PROBABILITY LOGIC
- 作者: Speranski S.1
-
隶属关系:
- Steklov Mathematical Institute of Russian Academy of Sciences
- 期: 卷 510, 编号 1 (2023)
- 页面: 8-12
- 栏目: МАТЕМАТИКА
- URL: https://journals.rcsi.science/2686-9543/article/view/134353
- DOI: https://doi.org/10.31857/S2686954323600040
- EDN: https://elibrary.ru/XHTJMV
- ID: 134353
如何引用文章
开放存取
##reader.subscriptionAccessGranted##
订阅存取
详细
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.
作者简介
S. Speranski
Steklov Mathematical Institute of Russian Academy of Sciences
编辑信件的主要联系方式.
Email: katze.tail@gmail.com
Russian Federation, Moscow
参考
- 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).
