КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер проекта 21-11-00318
НазваниеПроблемы вычислимости, доказуемости и полноты в логике и алгебре
Руководитель Беклемишев Лев Дмитриевич, Доктор физико-математических наук
Организация финансирования, регион Федеральное государственное бюджетное учреждение науки Математический институт им. В.А. Стеклова Российской академии наук , г Москва
Конкурс №55 - Конкурс 2021 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-101 - Математическая логика и основания математики
Ключевые слова формальная арифметика, периодическая группа, преобразование запросов, арифметика Пресбургера, теория доказательств, схема рефлексии, сложность вычислений, алгебра Клини, семантика, инфинитарная логика
Код ГРНТИ27.03.19
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
Проект связывает воедино ряд направлений исследований, проводимых в отделе математической логики МИАН и в группе логиков из ИППИ РАН. В проекте представлены исследования по комбинаторной и геометрической теории групп, теории сложности вычислений, исследования выразительных возможностей логических языков, в том числе применяемых в базах данных. С другой стороны, алгебраические методы применяются для изучения вычислительных моделей (алгебры Клини) и формальных моделей доказуемости (алгебры рефлексии). С алгоритмической точки зрения и с точки зрения семантики исследуется ряд важных классов неклассических логик, в том числе модальные логики и вероятностные логики. Важную роль в проекте также играет исследование новых типов моделей для предикатных модальных логик, обобщающих модели Крипке. Ниже перечислены основные задачи, рассматриваемые в проекте.
Исследование групп, заданных множеством периодических определяющих соотношений одного и того же достаточно большого периода. Этот класс групп является естественным обобщением свободных бернсайдовых групп, занимающих важное место в комбинаторной теории групп.
Исследование сложности задачи поиска ответов на запросы к базам данных, снабженным логической теорией.
Исследование логических теорий для алгебраических структур с итерацией Клини, прежде всего с точки зрения их алгоритмической сложности.
Исследование определимости в разрешимых арифметических теориях, в частности в арифметике Пресбургера (полной теории натурального ряда с операцией сложения) и в её обогащении — арифметике Бюхи. Для арифметики Бюхи будет исследоваться гипотеза Виссера об интерпретациях таких теорий в себе. Также предполагается исследовать вопрос об описании линейных порядков, интерпретируемых в арифметике Пресбургера.
Применение алгебраических методов при исследовании формальных теорий, важных с точки зрения оснований математики (расширений формальной арифметики первого порядка, подсистем формальной арифметики второго порядка). На основе методов, тесно связанных с использованием схем рефлексии и соответствующих полурешеток с монотонными операторами, мы ожидаем получить описание характеристических ординалов для таких теорий и описание их арифметических следствий фиксированной логической сложности (и спектров консервативности). В частности, с этой точки зрения планируется исследовать автономные прогрессии Тьюринга-Фефермана и некоторые другие теории.
Исследование вероятностных логик, то есть формальных языков, в основе семантики которых лежат вероятностные пространства (конечно-аддитивные или счетно-аддитивные). В рамках проекта планируется изучить с алгоритмической точки зрения теории некоторых важных классов конечно-аддитивных вероятностных пространств.
Исследование алгебраической и окрестностной семантик различных логик, допускающих нефундированные доказательства и доказательства с омега-правилом, в частности для логик с операторами взятия неподвижных точек и логик доказуемости.
Построение и исследование эффективных фрагментов модальных логик и других родственных логических языков. Изучение семантических и алгоритмических свойств предикатных модальных логик. Изучение топологической семантики модальных логик.
ОТЧЁТНЫЕ МАТЕРИАЛЫ
Публикации
1. Кузнецов С.Л. Reasoning in commutative Kleene algebras from *-free hypotheses The Logica Yearbook 2021, The Logica Yearbook 2021, College Publications, London, 2022, pp. 99-113 (год публикации - 2022)
2.
Шамканов Д.С.
On algebraic and topological semantics of the modal logic of common knowledge S4CI
Logic Journal of the IGPL, Published online, jzac075 (год публикации - 2022)
10.1093/jigpal/jzac075
3.
Чистопольская А.И., Подольский В.В.
On the decision tree complexity of threshold functions
Theory of Computing Systems, Vol. 66, N 6, P. 1074-1098 (год публикации - 2022)
10.1007/s00224-022-10084-x
4.
Беклемишев Л.Д.
Спектры консервативности и модель Йоостена-Фернандеса
Доклады Российской академии наук. Математика, информатика, процессы управления, T. 505, № 1, стр. 5-10 (год публикации - 2022)
10.1134/S1064562422040032
5.
Сперанский С.О.
Some remarks on Došen's logic N and its extensions
Сибирские электронные математические известия, Том 19, № 2, стр. 562-577 (год публикации - 2022)
10.33048/semi.2022.19.047
Публикации
1. Кузнецов С.Л. Алгоритмическая сложность теорий коммутативных алгебр Клини Известия РАН. Серия математическая (год публикации - 2024)
2. Кудинов А.В. Топологическое произведение модальных логик с аксиомой Маккинси Доклады Российской академии наук. Математика, информатика, процессы управления (год публикации - 2024)
3.
Сперанский С.О.
Элементарные инварианты для кванторной вероятностной логики
Доклады Российской академии наук. Математика, информатика, процессы управления, Том 510, сс. 8–12. (год публикации - 2023)
10.1134/S1064562423700667
4.
Шехтман В.Б., Шкатов Д.П.
Полупроизведения, произведения и предикатные логики: некоторые примеры
Доклады Российской академии наук. Математика, информатика, процессы управления, том 513, с. 98-106 (год публикации - 2023)
10.31857/S2686954323600325
5. Дворкин Л.В. О логиках доказуемости арифметики Нибергалля Известия РАН. Серия математическая (год публикации - 2024)