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

• Сафонов, Константин Владимирович
• доктор физико-математических наук
• 2006

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

ВВЕДЕНИЕ.

0.1. Проблематика исследования.

0.2. О содержании диссертации.

ВСПОМОГАТЕЛЬНАЯ

ГЛАВА.

ГЛАВА 1. Контекстно-свободные языки, их синтаксический анализ и коммутативные образы.

1.1. Контекстно-свободные грамматики и порождаемые ими языки.

1.2. Идентификаторы языков программирования и их задание контекстно-свободными грамматиками.

1.3. Проблема синтаксического анализа кс-языков программирования.

1.4. Коммутативные образы (производящие функции) кс-языков.

ГЛАВА 2. Фундаментальные свойства коммутативных образов контекстно-свободных языков.

2.1. Решение проблемы установления алгебраичности суммы степенного ряда (коммутативного образа формального языка).

2.2. Коммутативные образы кс-языков: связь с линейными языками.

2.3. Коммутативные образы кс-языков как диагонали рядов Лорана рациональных функций.

2.4. Конструктивное представление и приближенное вычисление коммутативных образов кс-языков.

2.5. Фундаментальные свойства множеств сходимости коммутативных образов формальных языков.

ГЛАВА 3. Распознавание контекстно-свободных языков: необходимые условия.

3.1. Теорема Эйзенштейна для коммутативных образов кс-языков.

3.2. Условия для коммутативных образов, сгруппированных по однородным многочленам.

3.3. Условия для коммутативных образов, сгруппированных в ряды Гартогса.

ГЛАВА 4. Распознавание контекстно-свободных языков: достаточные условия для коммутативных образов.

4.1. Достаточное условие алгебраического продолжения коммутативного образа языка.

4.2. Композиция Адамара формальных языков и их коммутативных образов.

4.3. Кс-языки и композиция Адамара линейных языков.

4.4. Характер особенностей композиции Адамара линейных языков.

4.5. Диагонали линейных языков.

4.6. Композиция Адамара сгруппированных линейных языков.

ГЛАВА 5. Вычислительное распознавание контекстно-свободных языков и грамматик.

5.1. Решение проблемы вычислительного распознавания коммутативных образов кс-языков.

5.2. Аффинные кс-грамматики и кс-языки.

5.3. Опеределители Ганкеля и алгебраическая зависимость кс-языков.

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

0.1. Проблематика исследования

Фундаментальным свойством большинства языков программирования является принадлежность классу контекстно-свободных языков (кс-языков), которые были введены в 50-х годах прошлого века выдающимся американским лингвистом Н. Хомским, заложившим основы теории кс-языков [113-119]. Действительно, в описании языка программирования определяются действующие в нем правила подстановки (продукции), совокупность которых является контекстно-свободной грамматикой (кс-грамматикой), порождающей соответствующий кс-язык программирования (напр., [5-8,14, 22, 26, 27, 39, 41, 42, 46, 49, 53, 60, 65, 68, 70, 120]). Таким образом, основные аспекты проблематики, связанной с исследованием различных языков программирования (к их числу относятся проблемы определенности языка, его синтаксического и семантического анализа и др.), могут быть рассмотрены с общей точки зрения, а именно, применительно к изучению свойств кс-языков, определяемым следующим образом.

Пусть конечное множество X = . ,хп] терминальных символов (слов) языка, например, операторов языка программирования, букв, цифр и т.д., а У = {у1,. ,ут} — множество нетерминальных символов, необходимых для задания грамматики языка, у\ — символ (аксиома), означающий начало программы (предложения); на множестве X и У введены операции конкатенации и формальной суммы, а также умножения на элементы числового поля.

Рассмотрим кс-язык, порожденный совокупностью продукций (грамматикой):

У; ¡ц(х,у),.,у{ -)• ¡щ(х,у), г = 1,. ,т, (0.1) где /у (ж, у) - мономы от некоммутативных символьных переменных из X и У (левая часть продукций содержит единственный символ и применяется независимо от контекста, а потому грамматика называется кс-грамматикой); как отмечалось, у\ — выделенный символ, означающий начало программы (предложения).

Тогда грамматике сопоставляется система полиномиальных символьных уравнений у{ =р1(х,у), % = 1,.,т, (0.2) где

Рг(х,у) = /й(х,у) + . . . + /щ(х,у), которую будем называть системой уравнений Хомского-Щютценберже (грамматикой в форме Хомского-Щютценберже).

Пусть < г,ги > обозначает числовой коэффициент, с которым моном гу от некоммутативных переменных входит в формальный ряд или многочлен г. Система (0.2) называется собственной системой, если ее коэффициенты удовлетворяют следующим условиям. А именно, порождающая способность грамматики не уменьшится, если из правил подстановки исключить правила вида у; и у1 -> е, где е — пустая цепочка (играющая роль единицы относительно умножения мономов: ех = хе = х), что и приводит к возможности [149] рассматривать только собственные системы (0.2), правые части которых удовлетворяют условиям

Р1,е >= 0,<Рг,У] >= о, 1,3 = 1 ,.,771. (0.3)

Метод последовательных приближений для системы (0.2) состоит в следующем. Рассмотрим итерации символьного решения системы:

Г'=Й(«,»(Ч),»(Ч = (»}",.,®й>), к = 0,1./> = (0,.,0), которые дают, в частности, выражение переменной у\ (кс-языка) в виде формального степенного ряда

У\ = ^ < > Щ. (0.4) г

Первая компонента у\ решения (у1(х),. ,ут(х)) системы (0.2), полученного методом последовательных приближений в виде формальных степенных рядов от х\,.,хп является данным кс-языком, т.е. формальной суммой мономов — всех правильных предложений (программ) данного языка.

Мономы г^ от XI,. ,хп этого ряда являются всевозможными правильными предложениями (программами) этого языка, причем числовой коэффициент < т/1, г^ > при мономе равен числу выводов этого монома при всевозможных применениях грамматических правил [102].

Важнейший подкласс кс-языков образуют линейные, в частности, регулярные языки, для которых все многочены системы (0.2) — линейные, в частности, леволинейные по у] = 1,., т.

Пример. Рассмотрим собственную систему

2/1 = ад + жш,

У2 = %2У2Х3 + Х2Х3, для которой метод последовательных приближений дает решение:

Нетрудно проверить, что первая компонента решения представляется рядом таким образом, данный кс-язык (над словарем {х1,х2,хз}) состоит из предложений вида

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

До сих пор теория формальных языков (программирования) не дала ответ на следующий фундаментальный вопрос: каковы свойства кс-языка, как по заданному формальному ряду (0.4) определить, является у(0) = (0,0), у{1) = (0;зд), У{2) = (х1х2хз]х1х1 + х2х3), У® = {Х1Х2ХЗ + Х\х\х\ + х\х\ + х\х\),--- ли он кс-языком, т.е. порожден ли он кс-грамматикой - некоторой полиномиальной системой уравнений вида (0.2)? Как отличить его от формального набора мономов, не являющегося кс-языком (программирования)?

Заметим, что если набор мономов из терминальных символов конечен, то ответ тривиальный: существует конечный кс-язык

У1 —> - -., 2/1 —> равный формальной сумме этих мономов, а потому имеет смысл рассматривать вопрос лишь о бесконечном формальном языке.

В исследованиях, посвященных изучению проблем, связанных с классом кс-языков, указанный вопрос не изучен. Эти исследования были направлены, например, на решение следующих проблем: по заданной кс-грамматике в форме Хомского-Щютценберже, т.е. по коэффициентам заданной системы уравнений (0.2), определить, содержит ли порождаемый ею кс-язык заданный моном с ненулевым коэффициентом (алгоритмически разрешимая проблема), порождают ли две заданные грамматики, а фактически - две различные системы уравнений вида (0.2), один и тот же кс-язык (как оказалось, алгоритмически не разрешимая проблема) и др.

Исследователи неоднократно подчеркивали необходимость рассмотрения вопроса о характеризации (распознавании) кс-языков. Фактически, проблема распознавания кс-языков восходит к работам академика В.М. Глушкова (например, [39]), который писал, что при решении проблем теории кс-языков важно иметь критерии, с помощью которых можно выяснить, является ли данный язык контекстно-свободным или нет [39, с. 197].

При этом В.М. Глушков и его ученики уделяли большое внимание необходимым и, отдельно, достаточным условиям, позволяющим в определенных случаях установить принадлежность языка классу кс-языков.

Однако, несмотря на значительное число результатов, посвященных кс-языкам [25-38, 51, 58, 59, 78, 106, 125, 141-144, 153-158, 162-167], какие-либо условия, характеризующие эти языки (соответствующие формальные ряды), не были известны (исключение составляет, пожалуй, необходимое условие, которое дает лемма Бар-Хиллела [9]). Таким образом, одно из центральных понятий в теории программирования, а именно, понятие кс-языка, в течение полувека оставалось не достаточно изученным. В связи с изложенным необходимо сформулировать и рассмотреть проблему В.М. Глушкова распознавания кс-языков Хом-ского.

Применение методов дискретной математики не позволило решить целый ряд важных проблем, например, проблему беступикового синтаксического анализа таких языков, проблему изучения свойств таких языков по свойствам системы уравнений Хомского-Щютценберже (0.2) и многие другие.

Одним из основных препятствий для решения вопроса о характе-ризации (распознавании) кс-языков является тот факт, что и в более простом для исследования случае коммутативных переменных не было известно решение подобного вопроса, т.е. не были известны критерии, распознающие степенные ряды алгебраических функций.

В случае комплексных переменных у £ Ст,х £ Сп собственная система (0.2) имеет в окрестности нуля (0,0) £ (£т+п единственное голоморфное решение (у\(х),. ,ут{х)), компоненты у^х) которого — алгебраические функции. Действительно, записывая систему (0.2) в виде

Ф, у) = Уг~ Р»(®, У) = 0, г = 1,., т, (0.5) видим, что условия (0.3) равносильны тому, что

0,0) = 0,г = 1 = 5 дУз где 5ц - символ Кронекера, следовательно, собственная система удовлетворяет условию теоремы о неявном отображении (метод последовательных приближений дает в этом случае тейлоровские разложения голоморфных в окрестности нуля функций у{(х), % = 1,., т).

В настоящей диссертации на основе полученных новых результатов в области комплексного анализа получены новые методы распознавания кс-языков и изучения их свойств, что имеет значительную актуальность в теории программирования.

Цель работы состоит в получении новых методов распознавания кс-языков (в том числе, языков программирования) и изучения их свойств на основе исследования определяющей системы (0.2).

Методика исследования состоит в использовании методов алгебры, комплексного анализа и теории формальных грамматик.

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

1. Решена проблема В.М. Глушкова распознавания кс-языков Хом-ского (в том числе, языков программирования), указаны соответствующие вычислительные алгоритмы.

2. Получен ряд новых необходимых, а также достаточных условий принадлежности формального языка классу кс-языков.

3. Разработан алгоритм беступикового синтаксического анализа кс-языков (языков программирования), основанный на предложенном автором методе "мономиальных меток".

4. Решена проблема установления алгебраичности суммы степенного ряда — доказан критерий алгебраичности, обобобщающий известный критерий Кронекера о рациональности суммы степенного ряда (1881 г.); полученный результат используется в диссертации при исследовании кс-языков.

5. В соответствии со свойствами системы (0.2) введен широкий класс (нелинейных) аффинных кс-языков, для которых доказано, что они образуются из линейных языков над более широким терминальным множеством в результате простой "процедуры диагонализации"; тем самым частично решена проблема определения свойств кс-языка по системе уравнений Хомского-Щютценберже.

Все основные результаты диссертации являются новыми.

Теоретическая значимость. Полученные в диссертации результаты существенно развивают теорию кс-языков программирования. Они доказаны новыми для этой теории методами, которые могут быть полезными и в дальнейших исследованиях.

Практическая ценность. Предложенный алгоритм беступикового синтаксического анализа необходимо использовать при исследовании языков программирования. В частности, этим методом можно установить, однозначны ли программы любой заданной длины А7", что важно при разработке новых языков программирования; результаты дают принципиальную возможность вычислительного распознавания кс-языков, что позволяет решать новые задачи в теории кодирования информации.

Апробация работы. Результаты диссертации докладывались на научно-исследовательских семинарах в Красноярском государственном техническом университете, Красноярском, Новосибирском. Томском государственных университах, Институте математики им. С.Л. Соболева СО РАН, Институте динамики систем и теории управления СО РАН, на Всесоюзных, Всероссийских и международных коферен-циях по комплексному анализу и его приложениям (1982-2003 г.г.), на Сибирских конгрессах по индустриальной и прикладной математике (1998 г., 2000 г.), на Международных и Всероссийских конференциях по математическим моделям и методам их исследования (1997-2003 гг.), на Сибирских научных школах-семинарах с международным участием по проблемам компьютерной безопасности и криптографии (2003 г., 2005 г.).

Публикации. По теме диссертации опубликовано более 30 работ, наиболее значительные из которых приведены ниже, из них 10 работ опубликованы в журналах, которые включены ВАК в Перечень ведущих научных рецензируемых изданий, а также в иностранных научных рецензируемых журналах.

0.2. О содержании диссертации

Список литературы диссертационного исследования доктор физико-математических наук Сафонов, Константин Владимирович, 2006 год

1. Адаменко А.Н., Кучуков A.M. Логическое управление программирование и Visual Prolog. - СПб.: БХВ-Петербург. - 2003. - 992 с.

2. Айзенберг Л.А., Лейнартас Е.К. Многомерная композиция Ада-мара и ядра Сеге // Сиб. матем. журн. 1983. - Т. 24, No 3. - С. 3-10.

3. Айзенберг Л.А., Южаков А.П. Интеграьные представления и вычеты в многомерном комплексном анализе. Новосибирск: Наука. - 1979. - 366 с.

4. Арнольд В.И., Варченко А.Н., Гусейн-Заде С.М. Особенности дифференцируемых отображений. Т. 2. М.: Наука. - 1983. -335 с.

5. Арутюнова Н.Д. Предложение и его смысл. Логико-семантические проблемы. М.: Наука. - 1976. - 380 с.

6. Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты. М.: Вильяме. - 2001. - 135 с.

7. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир - 1978. - 352 с.

8. Ахо А., Хопфорт Д.Э., Ульман Дж. Структура данных и алгоритмы. М.: Вильяме. - 2000. - С. 225-257.

9. Бар-Хиллел И., Кашер А., Шамир Е. Меры синтаксической сложности. Кибернетический сборник. Нов. серия. Вып. 4. - Мир. -1967. - С. 219-227.

10. Бауэр Ф.Л., Гооз Г. Информатика. Т. 1. М: Мир. - 1990. - 324 с.

11. Бауэр Ф.Л., Гооз Г. Информатика. Т. 2. М.: Мир. - 1990. - 410 с.

12. Бейтмен Г., Эрдейи А. Высшие трансцендентные функции. Т. 2.- М.: Наука. 1965. - 294 с.

13. Белецкий М.И. Бесконтекстные и доминационные грамматики и связанные с ними алгоритмические проблемы / Кибернетика. Вып. 4. 1967. - С. 90-97.

14. Белоногов Г.Г., Кузнецов Б.А. Языковые средства автоматизированных информационных систем. М.: Наука. - 1983. - 380 с.

15. Беляев В.А. К вопросу о множествах сходимости двойных степенных рядов // Матем. сб. 1966. - Т. 71. N0 1. - С. 14-23.

16. Беляев В.А. О множествах сходимости и абсолютной сходимости степенных рядов многих переменных / Исследов. по соврем, пробл. конструктивн. теории функций: сборник научных трудов.- Баку: АН Азерб. ССР. 1965. - С. 407-412.

17. Бибербах Л. Аналитическое продолжение. М.: Наука. - 1967. -237 с.

18. Бохнер С., Мартин У.Т. Функции многих комплексных переменны. М.: ИЛ. - 1953. - 300 с.

19. Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь. - 1987. - 122 с.

20. Брюно А. Локальный метод нелинейного анализа дифференциальных уравнений. М.: Наука. - 1979. - 259 с.

21. Ван-дер-Варден Б.Л. Алгебра. М.: Наука. - 1973. - 368 с.

22. Вирт Н. Алгоритм + структуры данных = программы . М.: Мир. - 1985. - 342 с.

23. Владимиров B.C. Методы теории функций многих комплексных переменных . М.: Наука. - 1964. - 410 с.

24. Воробьев H.H. Теория рядов. М.: Наука. - 1975. - 368 с.

25. Гинзбург С., Грейбах Ш. Об инвариантности классов Нс-языков относительно некоторых отображений / Кибернетический сборник. Нов. серия. Вып. 5. - М.: Мир. - 1968. - С. 167-188.

26. Гинзбург С., Райе X. Два класса языков типа АЛГОЛ / Кибернетический сборник. Нов. серия. Вып. 6. - 1969. - С.114-145.

27. Гинзбург С., Роуз Дж. Характеристика машинных отображений / Кибернетический сборник. Нов. серия. Вып. 5. - 1968. - С. 128-137.

28. Гинзбург С., Роуз Дж. Об инвариантности классов относительно некоторых преобразований / Кибернетический сборник. Нов. серия. Вып. 5. - 1968. - С. 138-166.

29. Гинзбург С. Математическая теория контекстно-свободных языков. М. Мир. - 1970. - 325 с.

30. Гладкий A.B. Грамматики с линейной памятью // Алгебра и логика. 1963. - Т. 2. Вып. 5. - С. 43-55.

31. Гладкий A.B. Алгоритмическая природа инвариантных свойств грамматик непосредственно составляющих // Алгебра и логика. 1964. - Т. 3. Вып. 2. - С. 17-32.

32. Гладкий A.B. О сложности выводов в грамматиках непосредственно составляющих // Алгебра и логика. 1964. - Т. 3. Вып. 5-6. - С. 29-44.

33. Гладкий A.B. Некоторые алгоритмические проблемы для КС-грамматик // Алгебра и логика. 1965. - Т. 4. Вып. 1. - С. 3-13.

34. Гладкий A.B. Агоритмическая нераспознаваемость существенной неопределенности КС-языков // Алгебра и логика 1965. - Т. 4. Вып. 4. - С. 53—64.

35. Гладкий A.B. Прямое доказательство теоремы Мэтьюза // Алгебра и логика. 1965. - Т. 4. Вып. 5. - С. 60-70.

36. Гладкий A.B. Лекции по математической лингвистике для студентов НГУ. Новосибирск: НГУ. - 1966. - 256 с.

37. Гладкий A.B., Мельчук И.А. Элементы математической лингвистики. М.: Наука. - 1969. - 436 с.

38. Гладкий A.B. Формальные грамматики и языки. М.: Наука. -1973. 337 с.

39. Глушков В.М., Цейтлин Г.Е., Ющенко E.J1. Алгебра, языки, программирование. Киев: Наукова думка. - 1974. - 328 с.

40. Грифитс Ф., Харрис Дж. Принципы алгебраической геометрии. Тт. 1, 2. М.: Мир. - 1982. - 852 с.

41. Демьянков В.З. Специализированные теории интерпретации в вычислительной лингвистике. М.: МГУ. - 1988. - 87 с.

42. Демьянков В.З. Универсальная грамматика. Краткий словарь когнитивных терминов / Кубрякова Е.С., Демьянков В.З., Панкрац Ю.Г., Лузина Л. Г./ Под общ. ред. Е.С. Кубряковой. М.: МГУ. - 1996. - С. 181-185.

43. Диковский А.Я. О соотношении между классом всех контекстно-свободных языков и классом детерминированных контекстно-свободных языков // Алгебра и логика. — 1969. Т. 7. Вып. 1. - С. 34-42.

44. Диковский А.Я., Модина Л.С. Минимизация одной функции сложности в классе МП-автоматов и категориальные грамматики сложности три // Алгебра и логика. — 1968. Т. 7. Вып. 3. -С. 23-37.

45. Егорычев Г.П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука. - 1977. - 285 с.

46. Ершов А.П. Программирующая программа для быстродействующей электронной счетной машины. М.: Изд-во АН СССР. -1958. - 325 с.

47. Жданов О.Н., Цих А.К. Исследование кратных интегралов Меллина-Барнса с помощью многомерных вычетов // Сиб. ма-тем. журнал. Т. 39. No 2. - 1998. - С. 24—32.

48. Знаменский C.B., Майергойз JI.C. О степенных рядах от многих комплексных переменных / Голоморфные функции многих комплексных переменных: Сборник научных трудов. Красноярск, Ин-т физики СО АН СССР - С. 185-195.

49. Искусственный интеллект. Книга 2. Модели и методы: Справочник / Под ред. Д.А. Поспелова. М.: Радио и связь. - 1990. - 304 с.

50. Карпов Ю.Г. Теория и технология программирования. Основы построения трансляторов. СПб.:БХВ-Петербург. - 2005. - 272 с.

51. Кибрик А.Е. Проблема синтаксических отношений в универсальной грамматике. Вып. XI. М.: Прогресс. - 1982. - С. 5-36.

52. К лини С.К. Представление событий в нервных сетях и конечных автоматах / Автоматы: сборник научных трудов. М.: ИЛ. -1956. - С. 15-67.

53. Компаниец Р.И., Маньков Е.В., Филетов И.Е. Системное программирование. Основы построения трансляторов. СПб: Коро-напринт. - 2000. - 256 с.

54. Кони И.М., Элгот К.С., Райт Д.Б. / Кибернетический сборник. Нов. серия. Вып. 3. М.: ИЛ. - 1961. - С. 147-166.

55. Курош А.Г. Курс высшей алгебры. M.-JL: Гостехиздат. - 1962.- 347 с.

56. Лейрнатас Е.К. Об одном обобщении композиции Адамара на функции многих комплексных переменных // Сиб. матем. журн.- Т. 22. No 4. 1981. - С. 218-221.

57. Лейрнатас Е.К. Об одном обобщении композиции Адамара в Сп.- Матем. заметки. Т. 32. - 1982. - С. 477-482.

58. Летичевский А.А. Представление контекстно-свободных языков в автоматах с памятью типа push-down / Кибернетика. Вып. 2. -1965. С. 80-84.

59. Летичевский А.А. Синтаксис и семантика формальных языков / Кибернетика. Вып. 4. - 1968. - С. 71-79.

60. Льюис Ф., Розенкранц Д., Стринз Р. Теоретические основы проектирования компиляторов. — М.: Мир 1979. - 288 с.

61. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука.- 1965. 336 с.

62. Мамфорд Д. Алгебраическая геометрия. Т. 1. Комплексные проективные многообразия. М.: Мир. - 1979. - 256 с.

63. Маричев О.И. Метод вычисления интегралов от специальных функций. Минск: Наука и техника. - 1978. - 354 с.

64. Марков A.A. Теория алгорифмов. JI.-M.: Изд-во АН СССР. -1954. - 376 с.

65. Мартыненко Б.И. Языки трансляции. СПб.: СПбГУ. - 2004. -234 с.

66. Миролюбов A.A., Солдатов М.А. Линейные однородные разностные уравнения. М.: Наука. - 1981. - 208 с.

67. Мэтьюз Д. Разрывность и асимметрия в грамматиках непосредственно составляющих / Математическая лингвистика. М.: Мир. - 1964. - С. 150-159.

68. Наур Н. Алгоритмический язык АЛГОЛ-бО / Пересмотренное сообщение. М.: Мир. - 1965. - 245 с.

69. Никитина С.Е. Семантический анализ языка науки. М.: Наука. - 1987. - 128 с.

70. Опалева Э. Языки программирования и методы трансляции. -СПб.: BHV. 2005. - 480 с.

71. Ope О. Теория графов. М.: Наука. - 168 с.

72. Пассаре М., Цих А.К., Чешель A.A. Кратные интегралы Меллина-Бариса как периоды многообразий Калаби-Яу с несколькими модулями // Теор. и матем. физика. Т. 109. N0 3. - 1996. - С. 381-394.

73. Поляков В.Н. Синтез формальных моделей языка и смысла как проблема семантической обработки естественного языка // Новости искусственного интеллекта. 1997. N0 1. - С. 6-63.

74. Поспелов Д.А. Прикладная семантика и искусственный интеллект // программные продукты и системы. 1996. - N0 3. - С. 24-28.

75. Поспелов Д.А., Осипов Г.С. Введение в прикладную семиотику // Новости искусственного интеллекта. 2002. - N0 6. - С. 28-35.

76. Пуанкаре А. Избранные труды. Т. 1. Новые методы небесной механики. М.: Наука. - 1971. - 771 с.

77. Рудин У. Теория функций в единичном шаре из Сп. М.: Мир -1984. - 455 с.

78. Рябин М., Скотт Д. Конечные автоматы и проблемы их разрешения / Кибернетический сборник. Вып. 4. 1962. - С. 58-91.

79. Самойленко Л.Г. Об одном классе грамматик непосредственно составляющих / Кибернетика. Вып. 2. 1968. - С. 102-103.

80. Сафонов К.В. О множестве точек сходимости двойного степенного ряда // Известия вузов. Матем. 1982. - N0 6. - С. 48-52.

81. Сафонов К.В., Цих А.К. Об особенностях параметрического вычета Гротендика и диагонали двойного степенного ряда // Известия вузов. Матем. 1984. - No 4. - С. 51-58.

82. Сафонов К.В. Об особенностях двумерной композиции Адамара (Аннотацитя статьи) // Сиб. матем. журнал. 1985. - No 4. - С. 200.

83. Сафонов К.В. О условиях алгебраичности и рациональности суммы степенного ряда // Матем. заметки. 1987. - Т. 41. Вып. 3. -С. 325-332.

84. Safonov K.V. Holomorphic extension of two-dimensional Hadamard Product // Selecta Mathematica Soviética. 1989. - V. 8. No 1. -P. 23-30.

85. Сафонов К.В. Монодромия композиции Адамара рациональных функций / Вопросы математического анализа: сборник научных трудов. 1992. - Красноярск. - С. 63-67.

86. Сафонов К.В. О кратных степенных рядах неявнях и мероморф-ных функций многих переменных / Вопросы математического анализа: сборник научных трудов. — 1995. Красноярск. - С. 93-105.

87. Сафонов К.В. Степенные ряды неявных и мероморфных функций многих переменных / Математические модели и методы их исследования: труды международной конференции. 1997. - Красноярск. - С. 162-163.

88. Сафонов K.B. О порядках алгебраичности аналитических функций / Материалы Третьего Сибирского конгресса по прикладной и индустриальной математике. 1998. - Новосибирск. - С. 92-93.

89. Сафонов К.В. О кратных степенных рядах алгебраических и рациональных языков / 5-й Международный семинар-совещание "Кубатурные формулы и их приложения". 1999. - Красноярск.- С. 33-34.

90. Сафонов К.В. О кратных степенных рядах алгебраических и рациональных языков / Труды Международной конф. "Комплексный анализ и дифференциальные операторы" (К 150-летию C.B. Ковалевской). 2000. - Красноярск. - С. 127-133.

91. Safonov K.V. On power series of algebraic and rational functions in Cn // Journal of Math. Analysis and Applications. 2000. - V. 243.- P. 261-277.

92. Сафонов K.B. Ряды Тейлора алгебраических функций как диагонали рядов Лорана рациональных функций / Многомерный комплексный анализ: сборник научных трудов. 2002. - Красноярск.- С. 158-164.

93. Сафонов К.В. О распознавании контекстно-свободных грамматик // Вестник Томского государственного университета. Серия " Математика. Информатика. Кибернетика". 2003. - Прил. No 6. -С. 16-18.

94. Сафонов К.В. О представлении решений произвольных алгебраических уравнений рядами Лорана / Вопросы математического анализа: сборник научных трудов. 2004. - Красноярск. - С. 129— 132.

95. Сафонов К.В. Контекстно-свободные языки как диагонали линейных языков // Вестник Красноярского государственного технического университета. 2004. - Вып. 33. - Красноясрк. - С. 37-41.

96. Сафонов К.В. Проблемы синтаксического анализа и распознавания контекстно-своодных языков / Вопросы математического анализа: сборник научных трудов. 2005. - Красноярск. - С. 143155.

97. Сафонов К.В. Обобщение критерия Кронекера о рациональности суммы степенного ряда на алгебраические функции и его применение // Вестник Красноярского государственного университета. Серия "Физико-математические науки". 2005. - N0 1. - С. - 7680.

98. Сафонов К.В. Распознавание афинных контекстно-свободных языков // Вестник Томского государственного университета. Серия "Математика. Информатика. Кибернетика". 2005. - Прил. N0 14. - С. 26-30.

99. Сафонов К.В. О возможности вычислительного распознавания контекстно-свободных языков // Вычислительные технологии. -2005. Т. 10. N0 4. - С. 91-98.

100. Сафонов К.В. О синтаксическом анализе и свойствах формальных языков программирования // Вычислительные технологии.- 2005. Т. 10. Специальный выпуск. - С. 9-15.

101. Сафонов К.В. Аналитический подход в теории формальных языков программирования / Оптимизация, управление, интеллект: материалы всероссийской конференции "Математика, информатика, управление". Ч. 2. — Иркутск. 2005. - С. 228-232.

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

103. Спеньер Э. Алгебраическая топология. М.: Мир. - 1971. - 680 с.

104. Стоцкий Э.Д. О некоторых ограничениях на способ вывода непосредственно составляющих / ИТИ. Серия 2. Вып. 7. - 1967. -С. 35-38.

105. Стоцкий Э.Д. Порождающие грамматики и управление выводом / ИТИ. Серия 2. Вып. 10. - 1968. - С. 28-31.I

106. Стоцкий Э.Д. Понятие индекса в обобщенных -грамматиках / ИТИ. Серия 2. Вып. 4. - 1969. - С. 45-48.

107. Умемура X. Решение алгебраических уравнений с помощью тета-констант / Д. Мамфорд. Лекции о тета-функциях. М.: Мир. -1988. - С. 362-370.

108. Фам Ф. Введение в топологическое исследование особенностей Ландау. М.: Мир. - 1967. - 184 с.

109. Фитиалов С.Я. Об эквивалентности грамматик НС и грамматик зависимостей / Проблемы структурной лингвистики. М.: Наука.- 1968. С. 71-102.

110. Харви Р. Голоморфные цепи и их границы. М.: Мир. - 1979. -160 с.

111. Хованский А.Г. Многогранники Ньютона. Разрешение особенностей / Современные проблемы математики. Т. 22. М.: ВИНИТИ.- 1983. С. 207-239.

112. Херц М.М. Энтропия языков, порождаемая автоматной или контекстно-свободной грамматиками с однозначным выводом / ИТИ. Серия 2. Вып. 4. - 1969. - С.89-92.

113. Хомский Н. Синтаксические структуры / Новое в лингвистике.- Вып. 2. М.: Прогресс. С. 412-527.

114. Хомский Н. Три модели для описания языка / Кибернетический сборник: сб. перев. статей / М.: ИЛ. 1961. - Вып. 2. - С. 237-266.

115. Хомский Н. О некоторых формальных свойствах грамматик / Кибернетический сборник: сб. перев. статей / М.: ИЛ. 1962. - Вып. 5. - С. 279-311.

116. Хомский Н. Заметка о грамматиках непосредственно составляющих / Кибернетический сборник. Нов. серия. Вып. 5. М.: Мир.- 1962. С. 312-316.

117. Хомский Н. Логические основы лингвистической теории. — Биробиджан: ИП Тривиум. 2000. - 146 с.

118. Хомский Н., Шютценберже М.Н. Алгебраическая теория контекстно-свободных языков / Кибернетический сборник. Нов. серия. Вып. 3. - М.: Мир. - 1966. - С. 195-242.

119. Хомский Н., Щютценберже М.П. Алгебраическая теория контекстно-свободных языков / Кибернетический сборник. Нов. серия. Вып. 2. - М.: Мир. - 1966. - С. 121-230.

120. Хопкрофт Дж.Э., Мортвани Р., Ульман Дж.Д. Введение в теорию автоматов, языков и вычислений. М.: Вильяме. - 2002. - 528 с.

121. Цих А.К. Критерии представимости интегралов по циклам локальными вычетами. Некоторые применения // Доклады АН СССР. 1984. - Т. 277. N0 5. - С. 1083-1085.

122. Чирка Е.М. Комплексные аналитические множества. М.: Наука.- 1985. 272 с.

123. Шабат Б.В. Введение в комплексный анализ. Ч. 2. М.: Наука. -1976. - 400 с.

124. Шейнов В.П. Критерий рациональности голоморфных функций двух комплексных переменных // Учен, записки МОПИ. 1966.- Т. 166. Вып. 10. с. 223-227.

125. Шрейдер Ю.А. Характеристики сложности структуры текста / ИТИ. Вып. 7. - 1996. - С. 34-39.

126. Южаков А.П. О применении кратного логарифмического вычета для разложения неявных функций в степенные ряды // Математический сборник. 1975. - Т. 97. No 2. - С. 177-192.

127. Южаков А.П., Цих А.К. О кратности нуля ситемы голоморфных функций // иб. матем. журн. 1978. - Т. 19. No 3. - С. 693-697.

128. Янушаускас А.И. Аналитические и гармонические функции многих переменных. Новосибирск: Наука. - 1983. - 183 с. '

129. Янушаускас А.И. Двойные ряды. Новосибирск: Наука. - 1990. -224 с.

130. Baker G.A. Approximate analitic continuation beyond the first Riemann sheet // Lect. Notes. Math. -1984. No 1105. - P. 285-294.

131. Bednarek A.R., Wallace A.D. A relation theoretic result with applications in topological algebra. Mathemetical System Theory.- 1. 1967. - No 3. - P. 12-34.

132. Deligne P. Integration sur une cycle evanescent // Invent. Math. -1984. No 1. - P. 129-143.

133. Djokovic D.Z. A property of the Taylor expansion of a class or rational function in several variables //J. of Math. Analysis and Appl. 1978.- V. 202. P. 34-40.

134. Falb L. Infinite-dimentional filtering // Information and Control. -V. 66. No 2. 1967. - P. 754-759.

135. Ficher P. Turing machines with a schedule to keep // Information and Control. V. 66. No 1. - P. 679-685.

136. Frechet M. Sur la limitation des consequences a tirer de l'évanouissement d'un wronskien // Bull. Math. 1936. - V. 3. -P. 105-109.

137. Gessel I.M. A factorization for formal Lourent series and lattice enumeration. J. Comb. Theory. - 1980. - A28. - P. 32-37.

138. Gilbert R.P., Howard H.C. Singularités of analitic function having integral representation, with remark about elastic //J. Math. Phys.- 1965.-No 7.-P. 1157-1162.

139. Give'on Y. On some properties of the free monoids with applications to automata theory. J. of Computer and System Sciences. -1977. -No 2. - P. 65-70.

140. Graham R. Subsemigroups of 0-simple semigroups // Mathemetical System Theory. 1967. - 3. - P. 41-47.

141. Griffiths P.A. On the periods of certain integrals. // Ann. Math. -1969. V. 90. No 3. - P. 460-495.

142. Hartmanis J. and Davis W.A. Homomorphic images of linear machines // J. of Computer and System Sciences. 1967. - 2. -P. 89-97.

143. Heller A. Stohastic transformations and automata. Mathemetical System Theory. - 1967. - No 3. - P. 68-73.

144. Horn G.M. Lexical-functional grammar. B.: Mouton. - 1983. - 238 P

145. Hibbard N., Gray J. and Harrison M. Scan limited automata and context limited limited grammars // Information and Control. 1969. -V. 11. No 1. - P. 5-14.

146. Mellin H.J. Resolutin de l'equation algebrique generale a l'aide de la fonction // C. R. Acad.Sc. V. 172. - 1921. - P. 658-661.

147. Nilsson N. Some growth and ramification properties of certain integrals on algebraic manifolds // Arkiv for Mathematic. Bd. 5. -Nr. 32. - 1963. - P. 463-476.

148. Rosenberg A.L. A machine realization of the linear context-free languages // Information and Control. 1977. - 10. - P. 175-188.

149. Rosenkrants D. Matrix equations and normal forms for context-free grammars //J. Assoc. Computing Machinery. 14. - 1967. - P. 501-507.

150. Salomaa A., Soittola M. Automata-Theoretics Aspects of Formal Power Series. N.Y.: Springer-Verlag. - 1978. - 288 p.

151. Samelson K, Bauer F.L. Sequential formula translation 11 Commun, of Algebra. 1985. - V. 21. - P. 45-50.

152. Scheinberg S. On property of context-free languages // Information and Control. 1960. - No 3. - P. 372-375.

153. Schorre D.V. A necessary and sufficient condition for a context-free grammar to be unambiguos / System Development Corporation Rept. SP-2153. - July 28. - 1965. - P. 154-156.

154. Schutzenberger M.P. Some remarks on Chomsky's context-free languages // M.L.T. Res. Lab. Electron Quart. Prog. Rept. 1961.- 23-56.

155. Schutzenberger M.P. Context-free languages and pushdown automata // Information and Control. 6. - 1963. - P. 246-264.

156. Schutzenberger M.P. Classification of Chomsky's languages // Proc. IFIP / Working Conference on Formal Language Description Languages. Baden. - 1964. - P. 76-79.

157. Shamir E. A remerk on discovery algorithms for grammars // Information and Control. 1962. - V. 5. - P. 246-251.

158. Shamir E. Mathematical models of languages // Procedings of IFIP Congress. Washington: Spartan Books. - 1965. - P. 17-75.

159. Shamir E.A. A presentation theorem for algebraic and context-free power series in non-commuting variables // Information and Control.- 1967. No 11. - P. 65-78.

160. Srivastava H.M., Karlson P.W. Multiple gausdsian Hypergeometric Series. New York: John Wilery. - 1985. - 252 p.

161. Soitola M. Positive rational sequences // Theoretical Computer Science. 1976. - V. 2. - P. 313-321.

162. Stearns R.E., Hartmanis J. Regularity preserving modifications of regular expressions // Information and Control. 1962. - V. 5. - P. 246-251.

163. Thatcher J.W. Characterizing derivation trees of context-free grammars through a generalization of finite automa ta theory //J. Computer and System Sciences. 1968. - No 1. - P. 132-138.

164. Ullman J.S. Failure of a conjecture about context-free languages // // Journal of Computer and System Sciences. 1967. - No 2. - P. 89-93.

165. Ullman J.D. Pushdown automata with bounded back-track / System Development Corp. Rept. 1966. - V. 9. - P. 61-65.

166. Ullman J.S. Partial algorithm problems for context-free languages // Information and Control. 1967. - V. 11. - P. 80-101.

167. Yntema M.K. Inclusion relations among families of context-free lamguages // Information and Control. 1967. - V. 10. - P. 572-597.

168. Younger D.H. Recognition and parsing of context-free languages in time n3 // Information and Control. 1967. - V. 10. - P. 598-605.