Аннотация:
Как известно, классические категориальные грамматики не способны выражать непроективные зависимости между словами в предложениях, когда зависимое слово стоит в "чужой" синтаксической группе. Одним из расширений категориальных грамматик являются категориальные грамматики зависимостей (КГЗ) и мультимодальные КГЗ (ммКГЗ), введённые в работах А.Я. Диковского и М.И. Дехтяря. Это классические категориальные грамматики, дополнительно оснащённые так называемыми поляризованными валентностями, задающими начала и концы непроективных зависимостей. КГЗ весьма выразительны, в частности, они способны порождать некоторые языки, не задаваемые комбинаторными категориальными грамматиками. Однако были неизвестны примеры "простых" языков, не порождаемых КГЗ. Данный доклад посвящён решению этой проблемы. Для КГЗ-языков будет доказано необходимое условие, являющееся обобщением леммы об обмене для контекстно-свободных языков (interchange lemma). С помощью этой леммы будет доказано, что язык копий не порождается никакой КГЗ, что класс КГЗ-языков не замкнут относительно пересечения и дополнения, а также что существует ммКГЗ-язык, не являющийся КГЗ-языком.
|
