Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
К приложению I.
Понятие системы составляющих восходит к грамматической традиции английского языка и американскому структурализму («анализ по непосредственным составляющим»; см. [Bloomfield 1933], [Harris 1961] и в особенности [Wells 1947]). Понятия степени левого и правого ветвления идут от работы В. Ингве [Yngve I960]; строго формально эти понятия впервые введены, видимо, в [Bar-Hillel—Kasher—Shamir 1963]. Понятие степени гнездования введено Н. Хомским [Chomsky 1961]; мы пользуемся этим понятием в видоизмененной форме, данной в [Bar-Hillel — Kasher — Shamir 1963] (эта форма не равносильна первоначальной). Понятие дерева синтаксического подчинения восходит к русской грамматической традиции; в явном виде оно впервые появилось (как часть некоторого более сложного понятия) у Л. Теньера [Tesniere 1959]. Идеи, приведшие к понятиям проективности и слабой проективности, впервые были — в неявной форме — высказаны Г. С. Цейтиным (см. [Цей-тин — Засорина 1961]) и независимо К. Харпером и Д. Хейсом [Harper — Hays 1960]. В явном виде эти понятия ввели, независимо друг от друга, И. Лесерф [Lecerf 1960}f М. И. Белецкий [Белецкий 1961] и С. Я. Фитиалов [Фитиалов 1962]. (Общепринятые сейчас формулировки, приводимые и в настоящей книге, принадлежат С. Я. Фитиа-лову.) Проективность изучалась с формальной и лингвистической'точек зрения, в частности, в [Белецкий — Григорян — Заславский 1963],
*) Содержание этой статьи изложено также в книге [Ginsburg 1966] (гл. 6).
348
БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ
[Дрейзин 1963], [Иорданская 1967]. Описанный в § П1.3 способ установления соответствия между системами составляющих и деревьями подчинения указан в [Падучева 1964] (в неформальном виде; формализованное изложение — в [Гладкий 1966]).
К приложению II.
Начало теории замещаемости было положено работой [Кулагина 1958]. В этой работе было, в частности, введено понятие конфигурации. Определение конфигурации, изложенное в настоящей книге, — основанное на тех же идеях, что и первоначальное определение О. С. Кулагиной, но не равносильное ему, — дано в [Гладкий 1963(a)]; там же введены понятия конфигурационных характеристик и конечно характеризуемого языка и получены теоремы ПП. 1 и ПП. 2*). Еще одно видоизменение понятия конфигурации было предложено М. Новотным [Novotny 1965(а, б, в)]. Лингвистическая критика конфигурационной модели имеется в [Падучева 1965], стимулированное в значительной степени этой критикой распространение понятия конфигурации на «языки деревьев» — в [Щербакова 1971]. Все основные понятия § ПП.З введены в [Кулагина 1958]; там же доказаны теоремы ПП.З—ПП. 6. Алгебраическое изложение этих понятий и результатов было дано Д. Н. Ленским [Ленской 1962] **) и М. Новотным [Новотный 1965]. Приведенные классы были введены (под именем «подклассов») И. И. Ревзиным [Ревзин 1962, 1967]. Анализирующим моделям посвящена книга [Marcus 1967], их лингвистическим приложениям — [Ревзин 1967].
*) При понимании конфигураций в смысле первоначального определения эти теоремы не имеют места.
**) На языке алгебры бинарных отношений (см. также [Шрейдер 1970]).
ЛИТЕРАТУРА
Барздинь Я. М. Сложность распознавания симметрии на машинах Тьюринга. — Сб. «Проблемы кибернетики», вып. 15, «Наука», 1965, 245—248.
Белецкий М. И. Модель языка алгоритма грамматического анализа. — Сб. «Тезисы Конференции по обработке информации, машинному переводу и автоматическому чтению текста», ВИНИТИ, 1961, 12.
Белецкий М. И. Бесконтекстные и доминационные грамматики и связанные с ними алгоритмические проблемы. — Кибернетика, 1967, № 4, 90—97.
Белецкий М. И., Григорян В. М., Заславский И. Д. Аксиоматическое описание порядка и управления слов в некоторых типах предложений. — Сб. «Математические вопросы кибернетики и вычислительной техники», № 1, Ереван, 1963, 71—85.
Борщев В. Б., Хомяков М. В. Окрестностные грамматики и модели перевода. Часть I. Окрестностйые грамматики. — Научно-техническая информация, сер. 2, 1970, № 3, 39—44.
Гладкий А. В. Конфигурационные характеристики языков. — Сб. «Проблемы кибернетики», выи. 10, Физматгиз, 1963(a), 251—260.
Гладкий А. В. О распознавании замещаемости в рекурсивных языках. — Алгебра и логика, 1963 (б), 2, № 3, 5—22.
Гладкий А. В. Грамматики с линейной памятью. — Алгебра и логика, 1963(b), 2, № 5, 43—55.
Гладкий А. В. Алгоритм распознавания конфигураций для класса автоматных языков. — Сб. «Проблемы кибернетики», вып. 12, «Наука», 1964(a), 243—245.
Гладкий А. В. Алгоритмическая природа инвариантных свойств грамматик непосредственно составляющих. — Алгебра и логика, 1964(6), 3, № 2, 17—32.
Гладкий А. В. О сложности вывода в грамматиках непосредственно составляющих. — Алгебра и логика, 1964(b), 3, № 5—6, 29—44.
Гладкий А. В. Некоторые алгоритмические проблемы для КС-грамматик. — Алгебра и логика, 1965(a), 4, № I, 3—13.
Гладкий А. В. Алгоритмическая нераспознаваемость существенной неопределенности КС-языков. — Алгебра и логика, 1965(6) 4, № 4, 53—64.
Гладкий А. В. Лекции по математической лингвистике для студентов НГУ, изд. Новосибирского гос. университета, 1966.
