Семинар Добрушинской лаборатории

Когда: вторник 6 октября, 16:15
Где: Адм.корпус, ауд.322.

Доклад:

Рыбаков Михаил (МФТИ),
"Логики, описывающие вычисления: их синтаксис, семантика и сложность \\ Logics describing computations: their syntax, semantics, and complexity"

Предполагается рассказать о формальных языках и логиках, предназначенных для описания свойств вычислительных процессов. Это прежде всего т.н. динамические пропозициональные логики (PDL, DPDL, IPDL и др.), а также такие темпоральные логики как LTL (linear-time temporal logic), CTL (computation tree logic) и ATL (alternating-time temporal logic). Все эти логики являются полимодальными, т.е. помимо логических средств классической логики высказываний содержат несколько (или даже бесконечно много) модальностей, позволяющих строить утверждения, касающиеся вычислений. Некоторые из таких модальностей называют также кванторами, и их связь с привычными кванторами всеобщности и существования будет показана. Модели этих логик связаны с процессами, развивающимися (дискретно) во времени, и, за редким исключением, предполагается, что время — ветвящееся. Причины такого допущения также предполагается обсудить (с примерами). Далее предполагается уделить внимание сложности проблемы разрешения рассматриваемых логик: будут приведены оценки сложности как для логик в полном языке, так и для некоторых их фрагментов (если успеем). При этом предполагается обсудить не только результаты о разрешимости, но и о неразрешимости, а также идеи, лежащие в основе сложностных оценок. Именно, мы посмотрим, какие условия в каких языках являются выразимыми (или невыразимыми), что даст содержательное представление о границах выразительных возможностей языков и их влиянии на сложность. Все необходимые определения будут даны.


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

Страницы семинара:
https://sites.google.com/view/dobr-seminar
https://www.mathnet.ru/conf167

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

#ВШМ_Добрушинский