#матлог #спецсеминар #нпммвя

В четверг 20 ноября в Институте языкознания РАН (с возможностью подключения онлайн) состоится заседание семинара «Некоторые применения математических методов в языкознании» с докладом Максима Евгеньевича Вишникина "Категориальные грамматики с ограничением на количество присваиваемых категорий".

Время: 20.11.2025, 14:00-15:30.
Место: Институт языкознания РАН, Большой Кисловский пер., 1, стр. 1, конференц-зал. Для прохода необходимо зарегистрироваться по ссылке ниже и взять с собой паспорт.

Ссылка для регистрации: https://forms.gle/RwXRf33JE3CP1bHBA
(все зарегистрировавшиеся получат ссылку для онлайн-подключения)

Тема: Категориальные грамматики с ограничением на количество присваиваемых категорий

Анонс:
В докладе будут рассмотрены три типа грамматических формализмов: грамматики Ламбека, AB-грамматики и базовые категориальные грамматики. Основное внимание будет уделено ограничению на количество присваиваемых категорий (параметр k) для каждого из них. Ключевой мотивацией для этого ограничения служит теория обучения грамматик по Голду, то есть задача идентификации грамматики по тексту. Эта концепция, введённая Марком Голдом в 1967 году, будет подробно изложена в первой части. Будут приведены известные результаты о том, что класс всех контекстно-свободных грамматик необучаем; однако при ограничении количества возможных правил полученный подкласс становится обучаемым (теорема Шинохары). Этот результат естественным образом распространяется на случай AB-грамматик (теорема Канадзавы).

В первой части доклада для трёх указанных формализмов будет представлен обзор результатов о классах грамматик с количеством категорий, ограниченным параметром k. Данное ограничение для AB-грамматик исследовал Канадзава, а для грамматик Ламбека — Форе. Также будут рассмотрены методы сведения языков, порождаемых различными грамматическими формализмами, друг к другу. В частности, теорема Сафиуллина, которая утверждает, что грамматики Ламбека с однозначным присвоением типов порождают все контекстно-свободные языки. Из данной теоремы сразу следует, что класс грамматик Ламбека с однозначным присвоением типов необучаем в смысле Голда.

Во второй части доклада будут рассмотрены алгоритмические свойства полученных классов грамматик. В частности, будут представлены результаты Форе, а также их усиление для AB-грамматик и базовых категориальных грамматик.

➰ ВК