ELEMENTARY INVARIANTS FOR QUANTIFIED PROBABILITY LOGIC

Мұқаба

Дәйексөз келтіру

Толық мәтін

Аннотация

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

Әдебиет тізімі

  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).

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу

© С.О. Сперанский, 2023

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).