Структурные свойства контекстно-свободных грамматик тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Горбунов, Константин Юрьевич

• Горбунов, Константин Юрьевич
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Горбунов, Константин Юрьевич

Введение

1. Основные определения.

§1.1. Определения ко второй главе

§1.2. Определения к третьей главе.

2. Перечислимые семейства контекстно-свободных грамматик

§2.1. Свойства преобразователей

§2.2. Свойства КС-грамматик.

3. Структурные свойства графовых КС-грамматик

§3.1. Понятие п-делимости графа и его свойства.

§3.2. Соотношение понятий п-делимости и древесной ширины графа.

§3.3. Основная теорема о структурных свойствах.

§3.4. Случай планарных графов.

§3.5. Применение к бесконечным графам.

Введение диссертации (часть автореферата) на тему «Структурные свойства контекстно-свободных грамматик»

Актуальность темы. Контекстно-свободные грамматики представляют собой исключительно важный тип грамматик, к которому пришли независимо друг от друга многие исследователи. Наиболее четкую и глубокую характеристику этого класса дал Н. Хомский [11], [12]. Важная роль КС-языков объясняется несколькими их особенностями:

• естественность методов порождения КС-языков с интуитивной точки зрения

• простота алгоритмов распознавания КС-языков

• возможность практического применения КС-языков при описании синтаксиса языков программирования и естественных языков

Идея КС-грамматик состоит в рассмотрении выводимого слова вместе с его выводом (точнее, деревом вывода), при этом вывод понимается как синтаксический анализ данного слова. Неединственность вывода на практике приводит к нарушению однозначности разбивки предложений языка на синтаксические единицы. Методы описания семантики языка и проверки корректности грамматики также предполагают ее синтаксическую однозначность. Поэтому, естественно потребовать единственность вывода, т.е. однозначность соответствующей КС-грамматики.

Класс однозначных КС-грамматик обладает лучшими алгоритмическими свойствами, чем класс всех КС-грамматик. Например, как показано в работе А. Л. Семенова [8], по произвольной однозначной КС-грамматике и произвольной регулярной КС-грамматике можно узнать, эквивалентны ли они (т.е. порождают ли они один и тот же язык). Как известно, для произвольных КС-грамматик проблема распознавания эквивалентности регулярной КС-грамматике не имеет решения.

С другой стороны, свойство КС-грамматики "быть однозначной" неразрешимо (см. например [4, стр. 307]). В связи с этим, в работе Ан. А. Мучника [7] поставлен следующий вопрос: можно ли перечислить какое-либо семейство однозначных КС-грамматик, порождающее все однозначные КС-языки? Если бы ответ был положительным, ситуацию можно было бы считать благоприятной.

Графовые контекстно-свободные грамматики, являясь обобщением словарных КС-грамматик, также имеют хорошие алгоритмические свойства. -Как заметил в работе [22] А. О. Слисенко, для семейства конечных графов,, выводимых в какой-то одной КС-грамматике, ряд известных проблем, КР-полны'х для произвольных графов, решается . за полиномиальное время (например, проблема существования в графе гамильтонова цикла). Вопрос о том, выводим ли граф в фиксированной грамматике, тоже решается полиномиальным алгоритмом. Существует сформулированная Ан. А. Мучником проблема, универсальная в некотором смысле для упомянутых классических проблем и им аналогичных. Эта проблема состоит в том, чтобы выяснить, верна ли для данного графа формула, бескванторная часть которой состоит из предиката, распознаваемого машиной Тьюринга специального вида, работающей на графах с размеченными вершинами и перенумерованными при каждой вершине ребрами и имеющей ограниченное число посещений каждой вершины. Кванторы всеобщности и существования берутся по разметкам — компонентам исходной разметки. Универсальность данной проблемы состоит в том, что в указанном виде представляются основные известные NP-пoлныe проблемы распознавания свойств графа. Для выводимого семейства графов, как показал Ан. А. Мучник (не опубликовано), эта проблема полиномиально решима. С другой стороны, для семейства графов, имеющих в качестве миноров неограниченно большие плоские квадратные решетки, она МР-полна (граф

А является минором графа если каждой вершине из А можно поставить в соответствие ненулевой связный подграф графа В (причем разным вершинам — непересекающиеся подграфы) и каждому ребру графа А поставить в соответствие ребро графа В, соединяющее те два подграфа, которые соответствуют концам ребра из А).

Поэтому, представляет интерес независимая от грамматик харак-теризация графов, для которых КР-проблемы указанного типа решаются за полиномиальное время. Кроме того, поскольку степень ветвления всех графов, выводимых в одной КС-грамматике, ограничена, представляет интерес обобщение понятия КС-выводимости на семейства графов с неограниченной степенью ветвления. Так, Н. Робертсон и П. Д. Сеймур предложили в [17] понятие древесной ширины графа и доказали в [16],[19], что для всех г существует т = /(г) такое, что любой граф, не имеющий в качестве минора плоской решетки размера г х г, имеет древесную ширину < т. Функция /(г) в их доказательстве имеет неэлементарный рост. В 1991 г. автор опубликовал оценку 7П = ехр(ро1у(г)) и метод, позволяющий доказать эту оценку. В 1994 г. Н. Робертсон, П. Д. Сеймур и Р. Томас опубликовали в [21] доказательство оценки т = 29г5. Их метод гораздо сложнее, чем метод автора, хотя он позволил достичь в показателе степени лучшей константы (5).

Цель работы. Основной целью работы является:

1. Получение ответа на вопрос о существовании перечислимого семейства однозначных КС-грамматик, порождающих все однозначные КС-языки.

2. Улучшение известных оценок размера графовых КС-грамматик, порождающих графы, не содержащие в качестве миноров решетки данного размера.

Методы исследования. В работе используется техника представления линейных КС-грамматик через преобразователи. Также используются комбинаторные методы, в частности, теоремы Рамсея и Менгера.

Научная новизна. Результаты диссертации являются новыми и состоят в следующем:

1) Доказано, что не существует перечислимого семейства КС-грамматик, порождающего класс однозначных языков. Попутно построен некоторый интересный класс грамматик, для которых проблема эквивалентности с произвольной КС-грамматикой имеет решение.

2) Получены верхние оценки древесной ширины графов, не содержащих в качестве миноров плоских решеток данного размера г х г. При этом, для произвольных графов соответствующая оценка имеет вид ехр(ро1у(г)), а для планарных графов получена линейная оценка. Из этих оценок следуют соответствующие оценки на минимальный размер графовой КС-грамматики, порождающей все графы, имеющие ограниченную степень ветвления и не содержащие в качестве миноров решеток данного размера.

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные результаты могут быть полезны специалистам в математической лингвистике и теории графов.

Аппробация. Результаты диссертации докладывались и обсуждались на Научно-исследовательском семинаре по математической логике механико-математического факультета МГУ под руководством С. И. Адяна и В. А. Успенского (в 1998 г.), а также на Колмогоровском семинаре кафедры математической логики и теории алгоритмов мех.-мат. факультета МГУ под руководством Н. К. Верещагина, А. Л. Семенова и А. X. Шеня (в 1996 г.) и на совместном семинаре МИР АН и ВЦ РАН по теории сложности под руководством А. А. Разборова и С. П. Тарасова (в 1998 г.).

Структура и объем работы. Диссертация состоит из введения и трех глав, разбитых на девять параграфов. Текст диссертации изложен на 67 страницах. Список литературы содержит 26 наименований.

Список литературы диссертационного исследования кандидат физико-математических наук Горбунов, Константин Юрьевич, 1999 год

1. Брауэр В. Введение в теорию конечных автоматов / Пер. с нем. К. В. Рудакова. — М.: Радио и связь, 1987. — 392с., ил.

2. Гросс М., Лантен А. Теория формальных грамматик / Пер. с франц. И. А. Мельчука. — М.: Мир, 1971.

3. Емеличев В. А., Мельников О. И., Сарванов В. П., Тышкевич Р. И. Лекции по теории графов. — М.: Наука, 1990. — 384с.

4. Лаллеман Ж. Полугруппы и комбинаторные приложения / Пер. с англ. И. О. Корякова. — М.: Мир, 1985. — 440с., ил.

5. Рыбников К. А. Введение в комбинаторный анализ. — М.: Изд-во Моск. ун-та, 1985. — 308с.

6. Саломаа А. Жемчужины теории формальных языков / Пер. с англ. А. А. Мучника. — М.: Мир, 1986. — 159с., ил.

7. Мучник Ан. А. Применение метода Семенова к анализу структуры контекстно-свободных языков / В кн: Семиотические аспекты формализации интеллектуальной деятельности. Тезисы. М.: ВИНИТИ, 1985. — С. 212-214.

8. Семенов А. Л. Алгоритмические проблемы для степенных рядов и контекстно-свободных грамматик // Доклады Академии наук СССР. — 1973. — Т. 212, N1. — С. 50-52.

9. Bergmann Н. Ein Planaritatskriterium fiir endliche Graphen // Elem. Math. — 1982. — Vol. 37, N2. — P. 49-51.

10. Chomsky N. Three models for the description of language // IRE Transactions on information theory. — 1956. — IT-2. — P. 113-121. Русский перевод: Кибернетический сборник. — 1961. — Вып. 2.С. 237-266.

11. Chomsky N. On certain formal properties of grammars // Information and Control. — 1959. — Vol. 2, N2. — P. 137-167. Русский перевод: Кибернетический сборник. — 1962. — Вып. 5. — С. 279-312.]

12. Muchnik An. A. and Soprunov S. F. Decidability of monadic theories of countable structures and of their classes // The Journal of Symbolic Logic. — 1991. — Vol. 56, N3. — P. 1146-1147.

13. Parikh R. J. On context-free languages // Journal of the Association for Computing Machmary. — 1966. — Vol. 13, N4. — P. 570-580.

14. Robertson N. and Seymour P. D. Graph minors. I. Excluding a forest // Journal of Combinatorial Theory, Series B. — 1983. — Vol. 35. — P. 39-61.

15. Robertson N. and Seymour P. D. Graph minors. II. Algorithmic Aspects of Tree-Width // Journal of Algorithms. — 1986. — Vol. 7. — P. 309-322.

16. Robertson N. and Seymour P. D. Graph minors. III. Planar tree-width // Journal of Combinatorial Theory, Series B. — 1984. — Vol. 36. — P. 49-64.

17. Robertson N. and Seymour P. D. Graph minors. V. Excluding a planar graph // Journal of Combinatorial Theory, Series B. — 1986. — Vol. 41. — P. 92-114.

18. Robertson N. and Seymour P. D. Graph minors. X. Obstructions to t ree-decomposition // Journal of Combinatorial Theory, Series B. — 1991. — Vol. 52. — P. 153-190.

19. Robertson N., Seymour P. D. & Thomas R. Quickly excluding a planar graph // Journal of Combinatorial Theory, Series B. — 1994. — Vol. 62. — P. 323-348.

20. Slisenko A. O. Context-free grammars as a tool for describing polynomial-time subclasses of hard problems // Information Processing Letters. — 1982. — Vol. 14, N2. — P. 53-56.

21. Weber A. A decomposition theorem for finite-valued transducers and an application to the equivalence problem // In: Proc. MFCS 1988 (Lect. Notes Comput. Sci. — Vol. 324. — P. 552-562) Berlin Heidelberg New York: Springer 1988.

22. Vigna P. D. and Chezzi C. Context-free graph grammars // Information and Control — 1978. — Vol. 37, N2. — P. 207-233.

23. Горбунов К. Ю. He существует перечислимого семейства контекстно- свободных грамматик, порождающего класс однозначных языков // Математические заметки. — 1991. —Т. 50, Вып. 1. — С. 34-40.

24. Горбунов К. Ю. Контекстно-свободная выводимость графов, не реализующих плоскую решетку // Доклады Академии наук СССР. — 1991. — Т. 316, N2. — С. 270-274.