Выразительная сила категориальных грамматик с однозначным присвоением категорий

Категориальная грамматика – это классический формализм для описания формальных языков. Идея заключается в том, чтобы каждому символу присвоить одну или несколько категорий, и слово принадлежит языку порождающей грамматикой, если после замены каждого символа одной из своих категорий полученная последовательность сводится к некоторой целевой.
В данном докладе рассматривается подкласс категориальных грамматик, в которых каждому символу присвоена единственная категория. Это ограничение снижает выразительную мощность формализма (например, язык $a^+$ не может быть порожден). Главная цель – глубже понять, сколько выразительной мощности остается. Можно заметить, что даже если каждому символу назначена уникальная категория, это не означает полное отсутствие неоднозначности; последовательность категорий может иметь разные свертки, потому что все еще существует выбор, откуда в последовательности начать сокращение. Это наблюдение используется для доказательства того, что возможно закодировать любую контекстно-свободную грамматику в категориальную грамматику с единственным назначением категорий таким образом, чтобы слово w принадлежало языку контекстно-свободной грамматики тогда и только тогда, когда его кодирование находится в языке категориальной грамматики. Таким образом, в частности, получается усиление классической теоремы Грейбах о самом трудном языке.
Доклад основан на совместной работе с А.С. Охотиным.