а в среду пройдёт последний в 2024 году логический семинар лаборатории им. Манина.

Когда и где: среда 18 декабря, 14:30, ауд. РТ 113 (очно и без трансляции).

Докладчик: Андрей Кудинов

Тема: О сохранение сложности слаботранзитивных модальных логик с универсальной модальностью при добавлении аксиомы связности.

Аннотация:

Под сложностью проблемы выполнимости некоторой модальной логики L понимается сложность следующей массовой задачи: по данной формуле A определить выполнима формула A на некоторой шкале логики L. Эта задача является двойственной к задачи выводимости в логике, т.к. формула A выводима в L тогда и только тогда, когда формула \lnot A невыполнима на L-шкале. Сложностной класс PSPACE содержит все массовые задачи, которые можно решить на машине Тьюринга, которая использует не больше полинома от длины входа ячеек ленты в процессе выполнения.

Мы будем рассматривать слаботранзитивные логики, т.е. логики содержащие wK4 = K + \Box p \land p \to \Box \Box p.
Общезначимость этой логики соотвествует тому, что рефлексивное замыкание отношения - транзитивно.
Добавление универсальной модальности увеличивает выразительную силу языка. Добавление универсальной модальности рассматривалось в 90-е годы в работах Горанко и Пасси, а в работе Шехтмана было доказано, что в языке с универсальной модальностью можно выразить связность.

Мы покажем, что если проблема выполнимости для логики с универсальной модальностью некоторого класса слаботранзитивных шкал содержится в сложностном классе PSPACE, то добавление к этой логике аксиомы связности не выведет из класса PSPACE.


Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная.
В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите на kudinov.andrey@gmail.com заранее.
Заседание пройдет очно без трансляции

Сртаница семинара: https://www.mathnet.ru/rus/conf2559

#ВШМ_логический