Enviar artigo por via de e-mail ELEMENTARY INVARIANTS FOR QUANTIFIED PROBABILITY LOGIC
- Autores: Speranski S.O.1
-
Afiliações:
- Steklov Mathematical Institute of Russian Academy of Sciences
- Edição: Volume 510, Nº 1 (2023)
- Páginas: 8-12
- Seção: MATHEMATICS
- URL: https://rjeid.com/2686-9543/article/view/647852
- DOI: https://doi.org/10.31857/S2686954323600040
- EDN: https://elibrary.ru/XHTJMV
- ID: 647852
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
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.
Palavras-chave
Sobre autores
S. Speranski
Steklov Mathematical Institute of Russian Academy of Sciences
Autor responsável pela correspondência
Email: katze.tail@gmail.com
Russian Federation, Moscow
Bibliografia
- 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).
Arquivos suplementares
