Логический семинар лаборатории им. Манина Высшей школы современной математики

Когда: среда 17 сентября, 14:00
Где: Адм. корпус, ауд.322.

Доклад:

А.В. Кудинов,
"Об окрестностной полноте и сложности некоторых ненормальных модальных логик"

В эпистемической логике аксиома нормальности [](p->q) -> ([]p->[]q) соответствует замкнутости знаний агента относительно правила Modus Ponens. Это означает, что если агент знает некоторые факты, то он знает и все их логические следствия.

Данное свойство философы характеризуют как логическое всезнание агента и активно критикуют гипотезу о том, что агенты в реальности обладают таким свойством. Однако отказ от аксиомы нормальности ведёт к потере полноты относительно семантики Крипке.

В этом случае приходится прибегать к окрестностной семантики. Нормальную логику можно ослабить различными способами; мы рассмотрим различные варианты логик, более слабых, чем минимальная нормальная логика K. И обсудим как доказывается окрестносная полнота для них.

Для таких логик также представляет интерес вопрос их алгоритмической сложности. В отличие от большинства нормальных модальных логик (таких как K, K4, S4), для которых проблема выполнимости является PSPACE-полной, для некоторых логик слабее K она оказывается NP-полной.

В докладе будет рассказано, как с помощью аппарата окрестностной семантики доказывается принадлежность проблемы выполнимости для определённых логик классу NP. Изложение будет следовать работе M. Vardi "On the complexity of epistemic reasoning" (LICS, 1989).

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


Планируется интернет-трансляция по адресу:
https://telemost.yandex.ru/j/00084330909943
Регистрируйтесь вашей фамилией, а не псевдонимом!

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

Адрес: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Если у вас нет пропуска МФТИ, то на входе сообщайте, что идёте на наш семинар, и не забудьте паспорт.

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