Quantifying over events in probability logic: An introduction

АБВ
АБВ
АБВ

Обычная версия сайта

Приоритетные направления

по году

Тематика

28 июля 2026 г.

Ученые выяснили, почему во время COVID-19 одни носили маски, а другие - нет

Почему одни люди добровольно следуют новым правилам, а другие их игнорируют? Ученые НИУ ВШЭ выяснили, что дело не столько в готовности действовать сообща, как считалось раньше, сколько в способности сопереживать другим людям. Именно эмпатия лучше всего объяснила, почему во время пандемии COVID-19 одни люди носили маски добровольно, а другие — нет. Результаты исследования опубликованы в журнале Frontiers.

27 июля 2026 г.

Ускорение, точность и самокоррекция: ученые ФКН ВШЭ на международной конференции ICML-2026

Исследователи факультета компьютерных наук (ФКН) ВШЭ представили свои проекты в южнокорейском Сеуле на международной конференции по машинному обучению ICML 2026, одном из главных научных событий в своей области. Сразу несколько исследований сотрудников факультета были удостоены высокого статуса Spotlight .

27 июля 2026 г.

«Конференция усилила ощущение причастности к международному математическому сообществу»

С 13 по 17 июля на факультете математики НИУ ВШЭ прошла международная конференция «Модули, динамика и интегрируемость». Ее участниками стали известные ученые из России, США, Китая, Великобритании и других стран.

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации

?

Quantifying over events in probability logic: An introduction

Mathematical Structures in Computer Science. 2017. Vol. 27. No. 8. P. 1581–1600.

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

In this article we describe a bunch of probability logics with quantifiers over events, and develop primary techniques for proving computational complexity results (in terms of m-degrees) about these logics, mainly over discrete probability spaces. Also the article contains a comparison with some other probability logics and a discussion of interesting analogies with research in the metamathematics of Boolean algebras, demonstrating a number of attractive features and intuitive advantages of the present proposal.

Язык: английский

DOI

Complexity for probability logic with quantiﬁers over propositions

Сперанский С. О., Journal of Logic and Computation 2013 Vol. 23 No. 5 P. 1035–1055

In the present article, the quantifiers over propositions are first introduced into the language for reasoning about probability, then the complexity issues for validity problems dealing with the corresponding hierarchy of probabilistic sentences are investigated. We prove, among other things, the $\Pi^1_1$-completeness for the general validity and also indicate the least level in the hierarchy ...

Добавлено: 27 декабря 2025 г.

On the decision problem for quantified probability logics

Сперанский С. О., Izvestiya. Mathematics 2025 Vol. 89 No. 3 P. 193–211

Let QPL-e expand the quantifier-free ‘polynomial’ probability logic of [Fagin et al. 1990] by adding quantifiers over arbitrary events; it can be viewed as a one-sorted elementary language for reasoning about probability spaces. We prove that the $\Sigma_2$-fragment of the QPL-e-theory of finite spaces is hereditarily undecidable. By earlier observations, this implies that $\Pi_2$ is the ...

Добавлено: 26 декабря 2025 г.

An ‘elementary’ perspective on reasoning about probability spaces

Сперанский С. О., Logic Journal of the IGPL 2025 Vol. 33 No. 2 Article jzae042

This paper is concerned with a two-sorted probabilistic language, denoted by QPL, which contains quantifiers over events and over reals, and can be viewed as an elementary language for reasoning about probability spaces. The fragment of QPL containing only quantifiers over reals is a variant of the well-known ‘polynomial’ language from [Fagin et al. 1990, Section 6]. ...

Добавлено: 26 декабря 2025 г.

Sharpening complexity results in quantified probability logic

Сперанский С. О., Logic Journal of the IGPL 2025 Vol. 33 No. 3 Article jzae114

We shall be concerned with two natural expansions of the quantifier-free ‘polynomial’ probability logic of [Fagin et al. 1990]. One of these, denoted by QPL-e, is obtained by adding quantifiers over arbitrary events, and the other, denoted by p-QPL-e, uses quantifiers over propositional formulas — or equivalently, over events expressible by such formulas. The earlier proofs ...

Добавлено: 26 декабря 2025 г.