Laboratory of Mathematical Logic at PDMI

Понедельник, 22 декабря, комната 203. Начало в 15:00.

Докладчик: Борис Карлов (Тверь).

Тема: Свойства обобщенных категориальных грамматик зависимостей.

Abstract

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