3 июня в 18:10 состоится заседание научно-исследовательского семинара «С логической точки зрения» («From the Logical Point of View»).

Тема доклада: Логика SSL и ее сложность.

Докладчик: А.В. Кудинов (НИУ ВШЭ).

Аннотация: Доклад посвящён логике подмножеств пространства (Subset Space Logic, SSL) — бимодальной эпистемической логике с одной модальностью знания (K) и второй модальностью (\Box), соответствующей тому, что агент потратил какие-то ресурсы, чтобы увеличить свои знания. Вторую модальность можно воспринимать, как некоторую динамику, поэтому SSL можно отнести к динамической эпистемической логике.
Логика была введена в работе A. Dabrowski, L. S. Moss & R. Parikh «Topological reasoning and the logic of knowledge» (Annals of Pure and Applied Logic, 1996), где, в частности, были предложены её аксиоматизации для класса всех подмножеств и для класса топологических пространств. В работе была доказана финитная аппроксимируемость, дающая оценку сверху на сложность логики SSL, а именно, что SSL лежит в 2EXPTIME. Также очевидно, что SSL - PSPACE-трудна, т.к. в нее погружается логика S4. Более точные оценки долгое время были неизвестны.
В работе 2021 года (препринт был в 2019) Гертлингом и Кроммесом (Hertling, Krommes) было доказано, что SSL является EXPSPACE-полной.
В докладе мы сделаем короткое введение и постараемся дать представление о том, как доказываются результаты о сложности.
Все нужные определения и понятия будут даны, предварительные знания о сложности не требуются, но приветствуются.
_____________________

Ждём вас в кабинете А-117 или в Zoom!

Анонс и регистрация: https://llfp.hse.ru/announcements/1164883547.html