- Код статьи
- 10.31857/S2686954323600040-1
- DOI
- 10.31857/S2686954323600040
- Тип публикации
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 510 / Номер выпуска 1
- Страницы
- 8-12
- Аннотация
- Пусть QPL – предложенный в [8] двусортный вероятностный язык, который расширяет хорошо известный “полиномиальный” язык, описанный в [3, раздел 6], посредством добавления кванторов по событиям. Мы показываем, что все безатомные пространства имеют одну и ту же QPL-теорию и эта теория разрешима. Также мы вводим понятие элементарного инварианта для QPL и используем его для получения точных верхних оценок на сложность некоторых интересных вероятностных теорий.
- Ключевые слова
- вероятностная логика квантификация по событиям элементарные инварианты сложность
- Дата публикации
- 17.09.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 11
Библиография
- 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).
