?
Неразрешимость модальных предикатных логик в языке с одной одноместной буквой
С. 41-43.
Рассматриваются предикатные модальные логики с одним одноместным предикатом. Показано, что соответствующие фрагменты подлогик таких логик как QS5, QGL или QGrz неразрешимы.
Язык:
русский
В книге
М. : Современные тетради, 2017
Рыбаков М. Н., Логические исследования 2017 Т. 23 № 2 С. 60-75
Рассматриваются модальные предикатные логики в языке, содержащем только одноместные предикатные буквы. Показано, что любая логика, содержащаяся в QS5, QGLLin или QGrz.3 является алгоритмически неразрешимой в языке с одной одноместной предикатной буквой (как при наличии, так и при отсутствии в логике формулы Баркан). Также показано, что логики конечных шкал Крипке (как с расширяющимися, так и с ...
Добавлено: 7 октября 2019 г.
Золин Е. Е., Journal of Logic and Computation 2017 Vol. 27 No. 5 P. 1399-1420
We extend the language of the modal logic K4 of transitive frames with two sorts of modalities. In addition to the usual possibility modality (which means that a formula holds in some successor of a given point), we consider graded modalities (a formula holds in at least n successors) and converse graded modalities (aformula holds ...
Добавлено: 14 июня 2018 г.
Кудинов А. В., Шапировский И. Б., В кн. : Сборник статей конференции Информационные технологии и системы (ИТиС'09). : М. : ИППИ РАН, 2009. С. 411-415.
В работе рассматриваются модальные логики бинарных отношений, удовлетворяющих условиям вида $R^m\subseteq R^n$. Несмотря на то, что эти логики легко описываются и имеют весьма простую аксиоматику, вопрос о финитной аппроксимируемости таких логик открыт. Эта задача возникла в 60х годах прошлого века (для случая m=3, n=2), и до сих пор остаётся нерешённой. В работе доказывается финитная ...
Добавлено: 27 февраля 2013 г.
Рыбаков М. Н., Вестник Тверского государственного университета. Серия: Прикладная математика 2018 № 4 С. 87-97
Исследуется вопрос о взаимосвязи между вычислительной сложностью проблемы разрешения модальной пропозициональной логики и сложностью контрмоделей для формул, которые ей не принадлежат. Известно, что для многих нормальных мономодальных пропозициональных логик разные исследователи применяли сходные конструкции для доказательства PSPACE-трудности проблемы разрешения логики и для обоснования нижних экспоненциальных оценок минимального числа элементов в шкалах Крипке, опровергающих формулы, не ...
Добавлено: 6 октября 2019 г.
Кудинов А. В., Шапировский И. Б., Известия РАН. Серия математическая 2017 Т. 81 № 3 С. 134-159
В работе доказана финитная аппроксимируемость и разрешимость семейства предтранзитивных модальных логик конечной высоты.
Построены специальные разбиения (фильтрации) предтранзитивных шкал конечной высоты, из чего следует финитная аппроксимируемость и разрешимость их модальных логик. ...
Добавлено: 4 сентября 2017 г.
Горбатов В. В., / Basic Research Programme. Series HUM "Humanities". 2016. No. 131.
Добавлено: 15 апреля 2016 г.
Shkatov D., Рыбаков М. Н., , in : Conference of the South African Institute of Computer Scientists and Information Technologists 2020 (SAICSIT '20). : ACM, 2020. P. 58-65.
Доказаны аналоги теоремы Чёрча и теоремы Трахтенброта для логики квазиарных предикатов. ...
Добавлено: 20 июля 2020 г.
Рыбаков М. Н., Шкатов Д. П., В кн. : Одиннадцатые Смирновские чтения по логике: материалы Международной научной конференции, 19 – 21 июня 2019, г. Москва. : М. : Современные тетради, 2019. С. 43-45.
Утверждается существование рекурсивно перечислимой полной по Крипке нормальной модальной предикатной логики, которая не полна относительно первопорядково определимых классов шкал, обсуждается контекст вопроса. ...
Добавлено: 6 октября 2019 г.
Kikot S., Шапировский И., Золин Е. Е., , in : Advances in Modal Logic. Vol. 13.: College Publications, 2020. P. 369-388.
Добавлено: 2 декабря 2020 г.
Семенов А. Л., Сопрунов С. Ф., Чебышевский сборник 2021 Т. 22 № 1(77) С. 304-327
В статье представлены результаты и открытые проблемы, относящиеся к пространствам определимости (редуктам), а также источникам этой области, начиная с XIX века. Исследуются условия конечности и ограничения, в том числе глубина чередования кванторов и число аргументов. Описаны результаты, относящиеся к описанию решеток пространств определимости для числовых и других естественных структур. Методы исследования включают изучение групп автоморфизмов ...
Добавлено: 11 марта 2023 г.
Кудинов А. В., В кн. : Сборник статей конференции Информационные технологии и системы (ИТиС'11). : М. : ИППИ РАН, 2011. С. 335-339.
Мы изучаем модальную логику с топологической модальностью и модальностью неравенства вещественной прямой и доказываем, что она финитно аппроксимируема и разрешима. ...
Добавлено: 27 февраля 2013 г.
Шехтман В. Б., Шапировский И. Б., В кн. : Современная логика: основания, предмет и перспективы развития. : М. : ИД "Форум", 2018. С. 265-305.
Модальная логика возникла в древности для формализации понятий возможного и необходимого.
Современная модальная логика стала одним из инструментов решения задач информатики --как теоретических, так и вполне прикладных.
Произошёл достаточно неожиданный переход из области абстрактных философских
категорий в актуальную и практически значимую современную дисциплину. Он был обусловлен тем, что модальная логика (как и логика в целом) приобрела развитый математический аппарат --- алгебраический, топологический, ...
Добавлено: 21 сентября 2018 г.
Kikot S., Shapirovsky I., Золин Е. Е., , in : Advances in Modal Logic. Volume 10. : College Publications, 2014. P. 333-352.
Фильтрация является стандартным средством для установления финитной аппроксимируемости модальных логик. В работе изучаются логики и классы шкал, допускающие фильтрацию (фильтруемые), и указываются операции на них, сохраняющие фильтруемость. В частности, показано, что операции добавления обратного отношения и транзитивного замыкания отношения сохраняет фильтруемость. Используя данные результаты, установлено, что всякая регулярная грамматическая модальная логика (возможно с обратными модальностями) ...
Добавлено: 14 июня 2018 г.
Захаров В. А., Cybernetics and Systems Analysis 2010 № 4 С. 39-48
В статье показано, каким образом двухленточные автоматы можно применять для проверки эквивалентности последовательных программ. Семантика последовательных программ определяется на основе моделей динамической логики. В том случае, когда динамическая шкала ациклична (т.е. в программе нет взаимно обратимых операторов), она может быть описана двухленточным детерминированным автоматом. Тогда задача проверки эквивалентности программ, семантика операторов которых определяется динамическими ...
Добавлено: 30 сентября 2015 г.
Условия разрешимости начальной задачи для систем нелинейных функционально-дифференциальных уравнений
Ларионов А. С., Симонов П. М., Шеина М. В., Вестник Тамбовского университета. Серия: Естественные и технические науки 2010 Т. 15 № 2 С. 542-549
Доказываются теоремы существования и единственности решения задачи Коши для систем нелинейных функционально-дифференциальных уравнений. При доказательстве теорем существенно используется положительность матрицы Коши соответствующей линейной системы. ...
Добавлено: 22 октября 2012 г.
Захаров В. А., Жайлауова Ш. Р., В кн. : Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019). : М. : Изд-во механико-математического факультета МГУ, 2019. С. 272-274.
В данной статье мы продолжаем поиск и исследование новых классов недетерминированных автоматов-преобразователей с разрешимой проблемой эквивалентности. Цель исследования~--- провести как можно более точную и подробную демаркацию границы между разрешимыми и неразрешимыми случаями проблемы эквивалентности для рассматриваемой модели вычислений. Мы рассматриваем один класс недетерминированных автоматов, работающих над выходным алфавитом из одной буквы. Характерная особенность рассматриваемых автоматов-преобразователей ...
Добавлено: 17 октября 2019 г.
Захаров В. А., Винарский Е. М., В кн. : Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019). : М. : Изд-во механико-математического факультета МГУ, 2019. С. 257-260.
Конечные автоматы Мили, представляющие собой простейшую математическую модель преобразования потоковых данных, широко используются во многих областях информатики. Но для некоторых приложений большое значение имеют не только значения обрабатываемых данных и порядок их следования, но также интервалы времени, которые отделяют события, присходящие по ходу вычисления автомата. Такие свойства уже не описывается явно средствами классической теории конечных ...
Добавлено: 17 октября 2019 г.
Дудаков С. М., Авхимович Н. В., Вестник Тверского государственного университета. Серия: Прикладная математика 2023 № 1 С. 24-35
В работе рассматриваются алгебраические системы, где в качестве носителя выступают конечные подмножества некоторой безатомной булевой алгебры. Для полученной системы мы вводим новое отношение для конечных подмножеств: считаем, что одно подмножество состоит в отношении с другим подмножеством в том и только том случае, когда все элементы одного подмножества меньше всех элементов другого. Мы демонстрируем, что теория ...
Добавлено: 12 ноября 2023 г.
Вялый М. Н., Рубцов А. А., Дискретный анализ и исследование операций 2012
Работа посвящена двум алгоритмическим задачам, связанным с анализом поведения конечного автомата при чтении сверхслова (бесконечной последовательности): достигает ли автомат принимающего состояния и достигает ли он принимающего состояния бесконечно часто. Первая задача возникает при анализе моделей обобщённого недетерминизма, а вторая – при анализе разрешимости монадических теорий второго порядка. Получены новые условия разрешимости для этих задач. Доказано, что всякая задача ...
Добавлено: 17 октября 2014 г.