?
Квантификация по пропозициональным формулам в вероятностной логике: вопросы разрешимости
Алгебра и логика. 2011. Т. 50. № 4. С. 533–546.
Language:
Russian
Speranski S. O., Математические заметки 2026 Т. 120 № 3 С. 470–483
We show that, in terms of closure ordinals, many infinitary calculi for ‘first-order’ logics of probability (i.e., for languages similar to those in [Abadi & Halpern 1994]) are as hard as possible: the corresponding closure ordinals coincide with the least non-constructive ordinal, denoted by $\omega_1^{\mathrm{CK}}$. ...
Added: August 12, 2026
Shehtman V. B., Gagarin A., , in: Graph Games and Logic Design. Recent Developments and Further Directions. (TREN, volume 66)Vol. 66.: Springer, 2026. Ch. 17 P. 419–450.
The chapter contains an overview of results on products of propositional modal logics and related constructions: semiproducts, Segerberg squares, and others. We focus mainly on axiomatizations, finite model property, and decidability; we also sketch connections with classical and modal predicate logics. In some cases we give ideas of proofs, especially of those using games. ...
Added: June 30, 2026
Springer, 2026.
This book presents established and new research on the close connections between graph games and systems of logic, particularly existing and newly designed modal logics. The volume utilizes two graph games – the sabotage game and the hide-and-seek game – to demonstrate the natural interplay between designing new graph games and exploring new kinds of ...
Added: June 30, 2026
Speranski S. O., Вестник Новосибирского государственного университета. Серия: Математика, механика, информатика 2011 Т. 11 № 4 С. 78–93
В настоящей статье изучаются вычислительные аспекты формального требования максимальной специфичности, накладываемого на правила в языке пропозициональной классической логики, когда над этим языком задана вычислимая рационально-значная вероятностная мера. Доказана неразрешимость ряда общих проблем по обнаружению максимально специфичных правил и вероятностных мер, для которых совокупность всех специфичных правил вычислима; установлена разрешимость множества максимально специфичных правил при неких ...
Added: December 27, 2025
Speranski S. O., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Added: December 27, 2025
Speranski S. O., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2023 Т. 510 С. 8–12
Пусть $\mathsf{QPL}$ – предложенный в [Speranski 2017] двусортный вероятностный язык, который расширяет хорошо известный «полиномиальный» язык, описанный в [Fagin et al. 1990, раздел 6], посредством добавления кванторов по событиям. Мы показываем, что все безатомные пространства имеют одну и ту же $\mathsf{QPL}$-теорию и эта теория разрешима. Также мы вводим понятие элементарного инварианта для QPL и используем его для ...
Added: December 26, 2025
Dudakov S., Авхимович Н. В., Вестник Тверского государственного университета. Серия: Прикладная математика 2023 № 1 С. 24–35
В работе рассматриваются алгебраические системы, где в качестве носителя выступают конечные подмножества некоторой безатомной булевой алгебры. Для полученной системы мы вводим новое отношение для конечных подмножеств: считаем, что одно подмножество состоит в отношении с другим подмножеством в том и только том случае, когда все элементы одного подмножества меньше всех элементов другого. Мы демонстрируем, что теория ...
Added: November 12, 2023
Semenov A., Сопрунов С. Ф., Чебышевский сборник 2021 Т. 22 № 1(77) С. 304–327
The article presents results and open problems related to definability spaces (reducts) and sources of this field since the XIX century. Finiteness conditions and constraints are investigated, including the depth of quantifier alternation and the number of arguments. Results related to the description of lattices of definability spaces for numerical and other natural structures are ...
Added: March 11, 2023
Kikot S., Shapirovsky I., Zolin E., , in: Advances in Modal LogicVol. 13.: College Publications, 2020. P. 369–388.
We give a sufficient condition for Kripke completeness of modal logics that have the transitive closure modality. More precisely, we show that if a modal logic admits what we call definable filtration, then its enrichment with the transitive closure modality (and the corresponding axioms) is Kripke complete; in addition, the resulting logic has the finite ...
Added: December 2, 2020
Shkatov D., Rybakov M., , in: Conference of the South African Institute of Computer Scientists and Information Technologists 2020 (SAICSIT '20).: ACM, 2020. P. 58–65.
It is proved that Church theorem and Trakhtenbrot theorem are true for the logic of quasiary predicates. ...
Added: July 20, 2020
Rybas A., Kostogryzov A., Grigoriev L. et al., , in: Proceedings 2018 Global Smart Industry Conference (GloSIC).: Chelyabinsk: IEEE, 2018. P. 1–7.
In the near future the possibilities of the modern probabilistic models, artificial intelligence and machine learning methods can provide an intelligent support of making decisions by an operator in real time. An agile recovery of intelligent manufacturing integrity can be implemented owing to the development of industrial robotics. For intelligent manufacturing it means the expected ...
Added: June 23, 2020
Zakharov V., Винарский Е. М., В кн.: Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019).: М.: Изд-во механико-математического факультета МГУ, 2019. С. 257–260.
Конечные автоматы Мили, представляющие собой простейшую математическую модель преобразования потоковых данных, широко используются во многих областях информатики. Но для некоторых приложений большое значение имеют не только значения обрабатываемых данных и порядок их следования, но также интервалы времени, которые отделяют события, присходящие по ходу вычисления автомата. Такие свойства уже не описывается явно средствами классической теории конечных ...
Added: October 17, 2019
Zakharov V., Жайлауова Ш. Р., В кн.: Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019).: М.: Изд-во механико-математического факультета МГУ, 2019. С. 272–274.
В данной статье мы продолжаем поиск и исследование новых классов недетерминированных автоматов-преобразователей с разрешимой проблемой эквивалентности. Цель исследования~--- провести как можно более точную и подробную демаркацию границы между разрешимыми и неразрешимыми случаями проблемы эквивалентности для рассматриваемой модели вычислений. Мы рассматриваем один класс недетерминированных автоматов, работающих над выходным алфавитом из одной буквы. Характерная особенность рассматриваемых автоматов-преобразователей ...
Added: October 17, 2019
Rybakov M., В кн.: Десятые Смирновские чтения: материалы Междунар. науч. конф., Москва, 15–17 июня 2017 г.: М.: Современные тетради, 2017. С. 41–43.
We consider first-order modal logics with unary predicate letters only. We show that any sublogic of QS5, QGL, or QGrz is undecidable in the language with just one unary predicate letter. Some near questions will be discussed. ...
Added: October 7, 2019
Rybakov M., Логические исследования 2017 Т. 23 № 2 С. 60–75
Рассматриваются модальные предикатные логики в языке, содержащем только одноместные предикатные буквы. Показано, что любая логика, содержащаяся в QS5, QGLLin или QGrz.3 является алгоритмически неразрешимой в языке с одной одноместной предикатной буквой (как при наличии, так и при отсутствии в логике формулы Баркан). Также показано, что логики конечных шкал Крипке (как с расширяющимися, так и с ...
Added: October 7, 2019
Rybakov M., Вестник Тверского государственного университета. Серия: Прикладная математика 2018 № 4 С. 87–97
Исследуется вопрос о взаимосвязи между вычислительной сложностью проблемы разрешения модальной пропозициональной логики и сложностью контрмоделей для формул, которые ей не принадлежат. Известно, что для многих нормальных мономодальных пропозициональных логик разные исследователи применяли сходные конструкции для доказательства PSPACE-трудности проблемы разрешения логики и для обоснования нижних экспоненциальных оценок минимального числа элементов в шкалах Крипке, опровергающих формулы, не ...
Added: October 6, 2019
Shehtman V. B., Шапировский И. Б., В кн.: Современная логика: основания, предмет и перспективы развития.: М.: ИД "Форум", 2018. С. 265–305.
Модальная логика возникла в древности для формализации понятий возможного и необходимого.
Современная модальная логика стала одним из инструментов решения задач информатики --как теоретических, так и вполне прикладных.
Произошёл достаточно неожиданный переход из области абстрактных философских
категорий в актуальную и практически значимую современную дисциплину. Он был обусловлен тем, что модальная логика (как и логика в целом) приобрела развитый математический аппарат --- алгебраический, топологический, ...
Added: September 21, 2018
Kikot S., Shapirovsky I., Zolin E., , in: Advances in Modal Logic. Volume 10.: College Publications, 2014. P. 333–352.
Filtration is a standard tool for establishing the finite model property of modal logics. We consider logics and classes of frames that admit filtration, and identify some operations on them that preserve this property. In particular, the operation of adding the inverse or the transitive closure of a relation is shown to be safe in ...
Added: June 14, 2018
Kudinov A., Шапировский И. Б., Известия РАН. Серия математическая 2017 Т. 81 № 3 С. 134–159
In this paper we prove the finite model property and decidability
of a family of pretrasitive modal logics of finite height. We construct special partitions (filtrations) of pretransitive
frames of finite height, which implies the finite model property and
decidability of their modal logics. ...
Added: September 4, 2017
Zakharov V., Cybernetics and Systems Analysis 2010 № 4 С. 39–48
This paper shows how two-tape automata can be employed to design efficient equivalence checking procedures for sequential programs. The semantics of sequential programs is defined in terms of dynamic logic structures. If a dynamic frame is acyclic (i.e., all program statements are irreversible), it can be specified by means of a two-tape deterministic automaton. Then ...
Added: September 30, 2015
Makeeva L., В кн.: Проблемы викладання логiки та дисциплiн логичного циклу. V Мiжнародна науково-практична конференцiя. Материалы доповiдей и виступiв.: К.: Киевский национальный университет им. Тараса Шевченко, 2012. С. 107–109.
Дается описание курса по индуктивной и вероятностной логике, который читается студентам философского факультета НИУ ВШЭ. ...
Added: March 12, 2015
Makeeva L., M.: ., 2014.
The present manual is written on the basis of the course on inductive logic which is delivered in English to philosophy students of National Research University Higher School of Economics. The manual describes the main approaches to constructing inductive logic; it clarifies its key notions and rules, and it formulates its major problems. This introductory ...
Added: March 9, 2015
Vyalyi M., Rubtsov A. A., Дискретный анализ и исследование операций 2012
Работа посвящена двум алгоритмическим задачам, связанным с анализом поведения конечного автомата при чтении сверхслова (бесконечной последовательности): достигает ли автомат принимающего состояния и достигает ли он принимающего состояния бесконечно часто. Первая задача возникает при анализе моделей обобщённого недетерминизма, а вторая – при анализе разрешимости монадических теорий второго порядка. Получены новые условия разрешимости для этих задач. Доказано, что всякая задача ...
Added: October 17, 2014