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

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