?
Computational properties of the logic of partial quasiary predicates
P. 58–65.
Shkatov D., Рыбаков М. Н.
Доказаны аналоги теоремы Чёрча и теоремы Трахтенброта для логики квазиарных предикатов.
Сперанский С. О., Вестник Новосибирского государственного университета. Серия: Математика, механика, информатика 2011 Т. 11 № 4 С. 78–93
В настоящей статье изучаются вычислительные аспекты формального требования максимальной специфичности, накладываемого на правила в языке пропозициональной классической логики, когда над этим языком задана вычислимая рационально-значная вероятностная мера. Доказана неразрешимость ряда общих проблем по обнаружению максимально специфичных правил и вероятностных мер, для которых совокупность всех специфичных правил вычислима; установлена разрешимость множества максимально специфичных правил при неких ...
Добавлено: 27 декабря 2025 г.
Сперанский С. О., Алгебра и логика 2011 Т. 50 № 4 С. 533–546
Язык для рассуждений о вероятности обобщается за счёт добавления в него кванторов по пропозициональным формулам. Далее рассматриваются соответствующие вопросы разрешимости. В частности, представленные результаты демонстрируют неразрешимость проблемы общезначимости для довольно слабого фрагмента нового языка. С другой стороны, устанавливается разрешимость ограниченной проблемы общезначимости для АЕ-предложений. ...
Добавлено: 27 декабря 2025 г.
Сперанский С. О., 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 г.
Сперанский С. О., Archive for Mathematical Logic 2013 Vol. 52 No. 5–6 P. 507–516
We carry out a study of definability issues in the standard models of Presburger and Skolem arithmetics (henceforth referred to simply as Presburger and Skolem arithmetics, for short, because we only deal with these models, not the theories, thus there is no risk of confusion) supplied with free unary predicates — which are strongly related to definability in ...
Добавлено: 27 декабря 2025 г.
Сперанский С. О., 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 г.
Сперанский С. О., 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 г.
Дудаков С. М., Авхимович Н. В., Вестник Тверского государственного университета. Серия: Прикладная математика 2023 № 1 С. 24–35
В работе рассматриваются алгебраические системы, где в качестве носителя выступают конечные подмножества некоторой безатомной булевой алгебры. Для полученной системы мы вводим новое отношение для конечных подмножеств: считаем, что одно подмножество состоит в отношении с другим подмножеством в том и только том случае, когда все элементы одного подмножества меньше всех элементов другого. Мы демонстрируем, что теория ...
Добавлено: 12 ноября 2023 г.
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2025 Vol. 35 No. 2 Article exad078
Добавлено: 3 ноября 2023 г.
Добавлено: 7 июля 2023 г.
Семенов А. Л., Сопрунов С. Ф., Чебышевский сборник 2021 Т. 22 № 1(77) С. 304–327
В статье представлены результаты и открытые проблемы, относящиеся к пространствам определимости (редуктам), а также источникам этой области, начиная с XIX века. Исследуются условия конечности и ограничения, в том числе глубина чередования кванторов и число аргументов. Описаны результаты, относящиеся к описанию решеток пространств определимости для числовых и других естественных структур. Методы исследования включают изучение групп автоморфизмов ...
Добавлено: 11 марта 2023 г.
Ломазова И. А., Vladimir A. Bashkin, Jančar P., Fundamenta Informaticae 2022 Vol. 186 No. 1-4 P. 175–194
Добавлено: 4 сентября 2022 г.
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2021 Vol. 31 No. 5 P. 1266–1288
Изучается алгоритмическая выразительность предикатных логик шкалы Крипке, задаваемой множеством натуральных чисел с отношениями порядка. ...
Добавлено: 23 января 2022 г.
Рыбаков М. Н., Shkatov D., Logic Journal of the IGPL 2022 Vol. 30 No. 3 P. 519–533
Добавлено: 29 мая 2021 г.
Kikot S., Шапировский И., Золин Е. Е., , in: Advances in Modal LogicVol. 13.: College Publications, 2020. P. 369–388.
Добавлено: 2 декабря 2020 г.
Рыбаков М. Н., Shkatov D., , in: Advances in Modal LogicVol. 13.: College Publications, 2020. P. 523–539.
Добавлено: 27 августа 2020 г.
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2020 Vol. 30 No. 7 P. 1305–1329
Добавлено: 27 августа 2020 г.
Жук Д. Н., Algebra Universalis 2014 Vol. 71 No. 1 P. 31–54
Добавлено: 15 июня 2020 г.
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2020 Vol. 30 No. 2 P. 549–560
Добавлено: 25 октября 2019 г.
Захаров В. А., Винарский Е. М., В кн.: Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019).: М.: Изд-во механико-математического факультета МГУ, 2019. С. 257–260.
Конечные автоматы Мили, представляющие собой простейшую математическую модель преобразования потоковых данных, широко используются во многих областях информатики. Но для некоторых приложений большое значение имеют не только значения обрабатываемых данных и порядок их следования, но также интервалы времени, которые отделяют события, присходящие по ходу вычисления автомата. Такие свойства уже не описывается явно средствами классической теории конечных ...
Добавлено: 17 октября 2019 г.
Захаров В. А., Жайлауова Ш. Р., В кн.: Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019).: М.: Изд-во механико-математического факультета МГУ, 2019. С. 272–274.
В данной статье мы продолжаем поиск и исследование новых классов недетерминированных автоматов-преобразователей с разрешимой проблемой эквивалентности. Цель исследования~--- провести как можно более точную и подробную демаркацию границы между разрешимыми и неразрешимыми случаями проблемы эквивалентности для рассматриваемой модели вычислений. Мы рассматриваем один класс недетерминированных автоматов, работающих над выходным алфавитом из одной буквы. Характерная особенность рассматриваемых автоматов-преобразователей ...
Добавлено: 17 октября 2019 г.