#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Семинар отдела математической логики МИАН, Logic Online Seminar (www.mathnet.ru/rus/conf876), понедельник 16:00 MSK (UTC+3), ауд. 313 + Kontur Talk

07.09.2026 Тихон Пшеницын (МИАН, https://www.mathnet.ru/person189359):
Аспекты сложности линейной логики и ее инфинитарных расширений

В докладе будет представлен обзор результатов докладчика о различных сложностных характеристиках субструктурных логик.

Первая серия результатов посвящена расширениям исчисления Ламбека с помощью итерации Клини, аксиоматизированной с помощью инфинитарного правила. Показано, что алгоритмическая задача доказуемости для некоторых таких расширений принадлежит гиперарифметической иерархии, а именно — является \Sigma^0_{\omega^\omega}-трудной (эта оценка является точной). Установлена также точная нижняя оценка \omega^\omega на замыкающий ординал для инфинитарной логики действий, что дает ответ на вопрос из статьи (Kuznetsov, Speranski 2022).

Вторая серия результатов связана с характеризацией сложности субструктурных логик методами теории формальных языков. Субструктурные логики лежат в основе категориальных грамматик — одного из подходов в теории формального синтаксиса. Как показал М.Р. Пентус, категориальные грамматики над исчислением Ламбека задают в точности контекстно-свободные языки без пустого слова. В статьях (Buszkowski, 1984), (van Benthem, 1991) был поставлен вопрос, верен ли аналогичный результат для коммутативных грамматик Ламбека, то есть категориальных грамматик над мультипликативным фрагментом интуиционистской линейной логики. На этот вопрос дается отрицательный ответ, а также устанавливается ряд свойств класса языков, задаваемых коммутативными грамматиками Ламбека, в том числе с использованием недавних результатов из статьи (Bizière, Leroux, Sutre 2026).