Развитие контекстно-зависимой грамматики - Growing context-sensitive grammar

В формальная теория языка, а растущая контекстно-зависимая грамматика это контекстно-зависимая грамматика в которых продукция увеличивает длину генерируемых предложений.[1][2] Таким образом, эти грамматики неконтрактный и контекстно-зависимый. А растущий контекстно-зависимый язык это контекстно-зависимый язык генерируется этими грамматиками.

В этих грамматиках «начальный символ» S не появляется с правой стороны любого производственного правила, а длина правой стороны каждого производственного правила превышает длину левой стороны, если только левая сторона не является S.[1]

Эти грамматики были введены Дальхаусом и Вармутом.[3] Позже было показано, что они эквивалентны ациклические контекстно-зависимые грамматики.[3] Членство в любом растущем контекстно-зависимом языке - это полиномиальное время вычислимый;[4][5] Однако униформа проблема определения, принадлежит ли данная строка к языку, генерируемому данной растущей[6] или ациклический[7] контекстно-зависимая грамматика НП-полный.

Смотрите также

Рекомендации

  1. ^ а б Дж. Бантрок и Ф. Отто (1995). «Развитие контекстно-зависимых языков и языков Чёрча-Россера». В Эрнст В. Майр и Клод Пуэх (ред.). Proc. 12-й СТЭКС. LNCS. 900. Springer. С. 313–324. ISBN  978-3540590422. Здесь: с.316-317
  2. ^ Герхард Бантрок и Фридрих Отто (1998). «Развитие контекстно-зависимых языков и языков Чёрча-Россера». Информация и вычисления. 141: 1–36. Дои:10.1006 / inco.1997.2681.
  3. ^ а б Гундула Ниманн и Йенс Р. Войновски (2002). «Растущие контекстно-зависимые языки являются ациклическими контекстно-зависимыми языками». У Вернера Куича и Гжегожа Розенберга и Арто Саломаа (ред.). Proc. 5-й Int. Конференция по развитию теории языков (DLT). Конспект лекций по информатике. 2295. Springer. С. 197–205. ISBN  978-3540434535.. Здесь: с.197-198
  4. ^ Э. Дальхаус и М.К. Вармут (1986). «Членство в растущих контекстно-зависимых грамматиках является полиномиальным». У Поля Франки-Заннеттаччи (ред.). Proc. 11-й коллоквиум по деревьям в алгебре и программировании (CAAP) (PDF). LNCS. 214. Springer. С. 85–99. Здесь: с.85-86
  5. ^ Э. Дальхаус и М.К. Вармут (1986). «Членство в растущих контекстно-зависимых грамматиках является полиномиальным». Журнал компьютерных и системных наук. 33 (3): 456–472. Дои:10.1016/0022-0000(86)90062-0.
  6. ^ Г. Бантрок и К. Лорис. О растущих контекстно-зависимых языках. В Proc. 19-й ICALP, LectureNotes in Computer Science (W. Kuich, ed, страницы 77–88. Springer-Verlag, 1992.
  7. ^ Эрик Аартс (1992). «Единое распознавание контекстно-зависимых грамматик является NP-полным» (PDF). Proc. 14-й Int. Конф. по компьютерной лингвистике (COLING, Нант, 23-28 августа). С. 1157–1161.

внешняя ссылка