?
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 of the complexity lower bound results for QPL-e and p-QPL-e relied heavily on multiplication, and therefore on the polynomiality of the basic parts. We shall obtain the same lower bounds for natural fragments of QPL-e and p-QPL-e in which only linear combinations of a very special form are allowed. Also, it will be studied what happens if we add quantifiers over reals.
Язык:
английский
Князева Е. Н., МЕТОД: Московский ежегодник трудов из обществоведческих дисциплин 2025 Т. 5 № 4 С. 176–182
В статье анализируется особенности творческой личности Владимира Ивановича Аршинова его стиля мышления, а также и его специфический вклад в философию науки – понятие сложностности. Сложность как ключевую характеристику самоорганизующихся систем Аршинов философски осмысливал в контексте постнеклассической науки и междисциплинарных исследований. Сложность предстает у него не просто как системная характеристика, а как онтологический принцип, задающий способ ...
Добавлено: 1 октября 2026 г.
The class of all ∗-continuous Kleene algebras, whose description includes an infinitary condition on the iteration operator, plays an important role in computer science. The complexity of reasoning in such algebras — ranging from the equational theory to the Horn one, with restricted fragments of the latter in between — was analyzed by Kozen (2002). This ...
Добавлено: 12 августа 2026 г.
Сперанский С. О., Математические заметки 2026 Т. 120 № 3 С. 470–483
Показывается, что с точки зрения замыкающих ординалов многие инфинитарные исчисления для «первопорядковых» логик вероятности (т.е. для языков, аналогичных языкам из [Abadi & Halpern 1994]) являются настолько трудными, насколько это возможно: соответствующие замыкающие ординалы совпадают с наименьшим неконструктивным ординалом, обозначаемым через $\omega_1^{\mathrm{CK}}$. ...
Добавлено: 12 августа 2026 г.
Сперанский С. О., Grefenshtein A., Izvestiya. Mathematics 2026 Vol. 90 No. 4 P. 754–775
The article is concerned with Halpern's first-order logics of probability, which we denote by L_1 and L_2 – the first of these deals with probability distributions on the domain, while the second employs distributions on external sets of possible worlds. The proofs of [Abadi & Halpern 1994] of the complexity lower bound results for L_1 and L_2 ...
Добавлено: 12 августа 2026 г.
David J. L., Leonid Grinin, Коротаев А. В., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 22 P. 585–608.
Добавлено: 10 августа 2026 г.
Коротаев А. В., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 13 P. 359–409.
Добавлено: 10 августа 2026 г.
Leonid Grinin, Alexander M., Коротаев А. В., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 12 P. 283–355.
Добавлено: 10 августа 2026 г.
David J. L., Leonid Grinin, Коротаев А. В., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 1 P. 1–25.
Добавлено: 10 августа 2026 г.
Дудаков С. М., Lobachevskii Journal of Mathematics 2025 Vol. 46 No. 12 P. 6092–6102
Добавлено: 1 мая 2026 г.
Тискин Д. Б., М.: Издательская группа URSS, 2026.
Предлагаемая книга представляет собой введение в формальную семантику — раздел языкознания, в котором посредством построения математически строгих моделей исследуется, как предложения приобретают значение и способность передавать информацию в зависимости от своей структуры и значений составляющих их слов. Классические теоретические идеи Г. Фреге, Д. Льюиса, Д. Каплана и др. излагаются современным языком, а при разработке нотации акцент сделан на том, ...
Добавлено: 17 марта 2026 г.
Добавлено: 16 февраля 2026 г.
Сперанский С. О., 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 г.
Сперанский С. О., Studia Logica 2017 Vol. 105 No. 2 P. 407–429
The paper contains a survey on the complexity of various truth hierarchies arising in Kripke’s theory. I present some new arguments, and use them to obtain a number of interesting generalisations of known results. These arguments are both relatively simple, involving only the basic machinery of constructive ordinals, and very general. ...
Добавлено: 26 декабря 2025 г.
Сперанский С. О., 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 ...
Добавлено: 26 декабря 2025 г.
Сперанский С. О., Journal of Logic and Computation 2021 Vol. 31 No. 5 P. 1330–1355
The idea of treating negation as a modality manifests itself in various logical systems, especially in Došen's propositional logic N, whose negation is weaker than that of Johansson's minimal logic. Among the interesting extensions of N are the propositional logics N* and Hype; the former was proposed in [Cabalar et al. 2006], while the latter has ...
Добавлено: 26 декабря 2025 г.
Кузнецов С. Л., Сперанский С. О., Annals of Pure and Applied Logic 2022 Vol. 173 No. 2 Article 103057
We introduce infinitary action logic with exponentiation — that is, the multiplicative-additive Lambek calculus extended with Kleene star and with a family of subexponential modalities, which allow some of the structural rules (contraction, weakening, permutation). The logic is presented in the form of an infinitary sequent calculus. We prove cut elimination and, in the case ...
Добавлено: 26 декабря 2025 г.