#матлог #учёба #спецсеминар

Семинар "Категориальные грамматики" продолжает работу.
Ближайший семинар состоится 24 октября (24.10.2024).

Начало: 18:30 (24.10.24). Аудитория: 424.

Докладчик: С.Л. Кузнецов
Тема: "Грамматики Ламбека с итерацией Клини"

Аннотация:
Теорема Пентуса утверждает, что категориальные грамматики Ламбека задают в точности контекстно-свободные языки. Выразительные возможности категориальных грамматик сильно возрастают, если к исчислению добавить новые операции. В докладе будут рассмотрены грамматики, основанные на исчислении Ламбека с итерацией Клини в двух вариантах её аксиоматизации: инфинитарном (омега-правило) и индуктивном. Также в рассматриваемых исчислениях присутствуют аддитивные конъюнкция и дизъюнкция. Для первого случая доказано, что соответствующие грамматики порождают в точности все ко-перечислимые языки. Для второго случая получены частичные результаты: грамматики с итерацией, аксиоматизируемой правилом индукции, порождают все разрешимые языки, а также хотя бы один \Sigma^0_1-полный язык. Будут также сформулированы открытые вопросы для дальнейших исследований.

Если вам необходим пропуск в МГУ, необходимо заранее связаться по почте max.startjob@gmail.com

➰ ВК