автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Теория направленных отношений и ее приложения

1. ТИПИЗИРОВАННЫЕ НАПРАВЛЕННЫЕ ОТНОШЕНИЯ.

1.1. Основные понятия.

1.2. Свойства ¿/-отношений.

1.3. Языки схем ¿/-отношений.

1.4. Классы ¿/-отношений.

1.5. Операции композиции ¿/-отношений.

1.6. Комбинаторные ¿/-отношения.

1.7. Дефинициональные расширения.

1.8. Основные сигнатуры.

1.9. Конструктивные ¿/-отношения.

1.9.1. Определение класса конструктивных ¿/-отношений.

1.9.2. Основные результаты.

1.10. Иерархия классов ¿/-отношений.

1.11. Исчисления включения и эквивалентности схем ¿/-отношений

1.11.1. Отношения включения и эквивалентности схем

-отношений.

1.11.2. Исчисление сильного включения ациклических схем ¿/-отношений.

1.11.3. Отношение включения рекурсивных схем ¿/-отношений

1.11.4. Отношение сильного включения схем конструктивных ¿/-отношений.

Основные результаты.

2. СЕТЕВАЯ ИНТЕРПРЕТАЦИЯ СХЕМ НАПРАВЛЕННЫХ

ОТНОШЕНИЙ.

2.1. Графические представления схем ¿/-отношений.

2.2. Базисы и сети.

2.3. Элементарные сети.

2.4. Операции композиции сетей.

2.5. Свободные и связанные сети. Вложение сетей.

2.6. Сетевые языки.

2.7. Сетевая интерпретация рекурсивных схем ¿/-отношений

2.8. Реляционная интерпретация сетевых языков.

2.9. Примеры задания сетевых языков и их реляционной интерпретации.

2.10. Формализация отношений реляционного включения и эквивалентности сетевых языков.

2.11. Примеры индуктивных доказательств эквивалентности сетевых языков в конструктивных базисах.

Основные результаты.

3. БЕСТИПОВЫЕ НАПРАВЛЕННЫЕ ОТНОШЕНИЯ.

3.1. Сигнатуры языков схем бестиповых ¿/-отношений.

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

3.3. Вычислительная полнота множества констант языка бестиповых регулярных схем ¿/-отношений основной универсальной сигнатуры.

Основные результаты.

4. ФУНКЦИОНАЛЬНЫЕ НАПРАВЛЕННЫЕ ОТНОШЕНИЯ.

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

4.2. Необходимые и достаточные условия функциональности.

4.3. Функциональные граф-схемы ¿/-отношений.

4.4. Модели вычислений функциональных ¿/-отношений.

4.4.1. Вычисление ¿/-отношений в конструктивных базисах.

4.4.2. Вычисление рекурсивных функциональных ¿/-отношений.

4.4.3. Вычисление ¿/-отношений, заданных функциональными граф-схемами.

Основные результаты.

5. НАПРАВЛЕННЫЕ ОТНОШЕНИЯ И ТЕОРИЯ СХЕМ ПРОГРАММ.

5.1. Стандартные и рекурсивные схемы программ.

5.2. Представление семантики схем программ средствами теории направленных отношений.

Основные результаты.

6. НАПРАВЛЕННЫЕ ОТНОШЕНИЯ И ЛОГИКА ПЕРВОГО

ПОРЯДКА

6.1. Трансляция схем направленных отношений в логический язык первого порядка.

6.2. Представление логических формул схемами направленных отношений.

6.3. Представление логических формул в исчислении сильного включения схем направленных отношений.

Основные результаты.

7. НАПРАВЛЕННЫЕ ОТНОШЕНИЯ И ЛОГИЧЕСКИЙ ВЫВОД

7.1. Метод сетевой резолюции.

7.2. Сетевая резолюция в логике первого порядка с равенством

7.3. Доказательство противоречивости системы включений как альтернатива резолютивному логическому выводу.

Основные результаты.

8. НАПРАВЛЕННЫЕ ОТНОШЕНИЯ И ФУНКЦИОНАЛЬНО

ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

8.1. Парадигмы функционального и логического программирования.

8.2. Общие принципы построения языка функционально-логического программирования FLOGOL.

8.3. Синтаксис языка FLOGOL.

8.4. Примеры программ на языке FLOGOL.

8.5. Архитектура и принципы реализации FLOGOL -системы функционально-логического программирования.

Основные результаты.

СПИСОК ОБОЗНАЧЕНИЙ.

СПИСОК СОКРАЩЕНИЙ.

ВЫВОДЫ

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

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

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

4. Класс рекурсивно определенных типизированных направленных отношений в базисе конструкторов и парных им деструкторов позволяет с точностью до кодирования выражать произвольные вычислимые функции.

5. Класс бестиповых направленных отношений, регулярных относительно конечного набора комбинаторных констант, также обладает статусом вычислительной полноты.

6. Введенные в работе понятия сети и сетевого языка являются наглядной адекватной формой представления схем направленных отношений, позволяющей эффективно решать многие задачи, связанные как с разработкой теории направленных отношений, так и с ее возможными приложениями.

7. Понятие сетевого языка в заданном базисе элементов является естественным обобщением понятия формального языка в заданном алфавите, позволяющим во многих случаях снизить уровень синтаксической сложности определения множества элементов языка за счет выхода во «второе измерение».

8. Предложенные средства задания практически важного подкласса функциональных схем направленных отношений допускают корректное применение ёага-Аомг-модет вычислений.

9. Характеризация базовых свойств направленных отношений в форме правил редукции сетей и сетевых языков позволяет построить корректные модели вычислений рекурсивно определенных направленных отношений в базисе конструкторов на эрбрановском универсуме.

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

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

12. Теория направленных отношений имеет тесную связь с логическими языками, прежде всего, с языками первого порядка, позволяющую по-новому интерпретировать известные процедуры логического вывода, в том числе и метод резолюции. В частности, оказывается возможным прямой вывод общезначимости формулы первого порядка, в явном виде не использующий с этой целью эрбрановской интерпретации; в качестве «побочного эффекта» процесса вывода строятся сетевые описания моделей рассматриваемой формулы, не зависящие от интерпретации предикатных символов.

13. Универсальность формализма направленных отношений позволила показать сводимость процедуры логического вывода методом резолюции к универсальным процедурам рекурсивной подстановки и нетеровской редукции сетевых языков, в которых прямые и инверсные предикатные символы рассматриваются как нетерминальные сорта элементов при задании сетевого языка, представляющего логическую формулу.

14. Сведение доказательства общезначимости формулы первого порядка к доказательству противоречивости конечной системы сильных реляционных включений для конечных множеств сетей дает возможность отказаться от представления в этих сетях инверсных литер логической формулы с помощью особых сортов элементов.

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

16. Основанный на теории направленных отношений язык функционально-логического программирования РЬОООЬ обладает развитыми средствами схемного определения различных объектов достаточно сложных предметных областей и формирования запросов на вычисления, используя технологические возможности, аналогичные тем, которыми располагают современные объекто-ориентированные1 языки программирования общего назначения.

17. Возможность определения схем направленных отношений в языке РЬОООЬ как в композиционной форме, так и в форме так называемых графиков, непосредственно связанной с сетевым представлением схем, позволяет использовать удобные и наглядные формы специального графического интерфейса при интерактивном программировании на этом языке.

18. Язык РЬОООЬ позволяет вносить в разрабатываемое описание предметной области дополнительную информацию о свойствах конкретной (внешне заданной) или всех допустимых (для не определяемых в языке объектов) интерпретаций, с целью обеспечения более высокой эффективности процесса выполнения запросов с использованием механизмов логического вывода.

19. Некоторые из предложенных и используемых в теории направленных отношений вспомогательных средств могут найти применение и в смежных об' ластях. Так, идеи сетевого представления были использованы для построения

1. Арефьев А.А. и др. Язык граф-схем параллельных алгоритмов и его расширения // Программирование, 1981. №4.

2. Барендрегт X. Ламбда-исчисление. Его синтаксис и семантика // М.: «Мир». 1985.

3. Борщев В.Б., Хомяков М.В. Окрестностные грамматики и модели перевода // Научно-техническая информация. Сер. 2, 1970. №3.

4. Борщев В.Б., Хомяков М.В. Клубные системы // Научно-техническая информация. Сер. 2, 1976. №8.

5. Борщев В.Б. Схемы на клубных системах и вегетативная машина // Семиотика и информатика. Вып.22, 1983.

6. Борщев В.Б. Логическое программирование // Известия АН СССР. Техническая кибернетика, 1986. №2.

7. Борщев В.Б. Семантика логических конструкций в логическом программировании // Логические методы в программировании. Вычислительные системы. Новосибирск, 1987.

8. Борщев В.Б. Вегетативная машина // Программирование, 1989. №5.

9. Борщев В.Б. Семантика языков логического программирования // ВИНИТИ. Итоги науки и техники. Вычислительные науки, том 4.1990.

10. БулосДж., Джеффри Р. Вычислимость и логика // «Мир». М., 1994.

11. ЛЛ.Бэкус Дж. Алгебра функциональных программ // «Математическая логика в программировании» (сб. статей). Москва, «Мир». 1991.

12. Вагин В.Н. Дедукция и обобщение в системах принятия решений // «Наука». М., 1988.

13. Вагин В.Н. Параллельная дедукция на семантических сетях // Изв. АН СССР. Техническая кибернетика, 1986. №5.

14. Гончаров С.С., Свириденко Д.И. £ -программирование // Вычислительные системы. Вып. 107. Новосибирск, 1985.

15. Грызунов В.Б. Разработка функционального языка программирования для персональных ЭВМ //Автореф. дис. на соиск. учен, степени канд. техн. наук. М. МЭИ, 1990.

16. Деннис Дж.Б. и др. Схемы потока данных//Труды симпозиума «Теория программирования». ВЦ СО АН СССР. Новосибирск, 1972.

17. М.Джафри А. Язык функциональных схем и параллельные алгоритмы // Программирование, 1977. №6.

18. Ершов Ю.Л. Язык Е-выражений II Вычислительные системы. Вып.116. Новосибирск, 1986.

19. Ершов Ю.Л. Теория А-пространств // Алгебра и логика. ИМ СО АН СССР, Новосибирск, 1973. Т. 11.

20. Жангисина Г.Д. Исследование и разработка специализированной базы математических знаний для систем функционального программирования // Автореф. дис. на соиск. учен, степени канд. техн. наук. Нац. АН Республики Казахстан. Алма-Ата, 1995.

21. Кораблин Ю.П. Языки параллельных алгоритмов и принципы их реализации //Автореф. дис. на соиск. учен, степени канд. техн. наук. М. МЭИ, 1977.

22. Кораблин Ю.П. «Семантические методы анализа распределенных систем» // Автореф. дис. на соиск. учен, степени докт. техн. наук. М. МЭИ, 1994.

23. Кораблин Ю.П., Кутепов В.П., Строева Т.М., Фальк В.Н. Языки параллельных алгоритмов и вопросы их реализации на многомашинных комплексах // Тез. докл. на респ. НТК по вопр. разраб. и внедр. средств ВТ и УВК в народное хозяйство. Тбилиси, 1977.

24. Кораблин Ю.П., Кутепов В.П., Фальк В.Н. Исчисление функциональных схем // В сб. «Цифровая вычислительная техника и программирование». «Советское радио», 1974. Вып. 8.

25. Кораблин Ю.П., Кутепов В.П., Фальк В.Н. Об одном аксиоматическом подходе к проблеме эквивалентных преобразований рекурсивных функциональных схем алгоритмов //Труды МЭИ. Вып. 244. М.,1975.

26. Котов В.Е. Введение в теорию схем программ // Наука. Новосибирск, 1978.

27. Котов В.Е. Алгебра регулярных сетей Петри // ВЦ СО АН СССР. Препринт № 98. Новосибирск, 1978.

28. Криницкий Н.А. Широкое формальное определение алгоритма // Проблемы киберенетики, 1977. Вып. 32.

29. Кутепов В.П. Исчисление функциональных схем и параллельные алгоритмы//Программирование, 1976. №6.

30. Кутепов В.П. Проблема функциональности в одном классе схем отношений //Кибернетика, 1981. №3.

31. Кутепов В.П. Функциональные системы и параллельные вычисления // Автореф. дис. на соиск. учен, степени докт. техн. наук. М. МЭИ, 1988.

32. Кутепов В.П. Об интеллектуальных компьютерах и больших компьютерных системах нового поколения // Изв. РАН. Теория и системы управления, 1996. №5.

33. Кутепов В.П., Фальк В.Н. Функциональные граф-схемы алгоритмов и их эквивалентные преобразования II Киев: Труды Первой Всесоюзной конференции по программированию. Изд. Института Кибернетики АН УССР, 1968.

34. Кутепов В.П., Фальк В.Н. Некоторые вопросы рациональной организации вычислений //Докл. НТК по итогам НИР за 1968-1969 г.г. МЭИ. М.,1970.

35. Кутепов В.П., Фальк В.Н. Модели асинхронных вычислений значений функций в языке функциональных схем // Программирование, 1978. №3.

36. Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты // Кибернетика, 1979. №1.

37. Кутепов В.П., Фальк В.Н. Направленные отношения: теория и приложения // Изв. РАН. Техническая кибернетика, 1994. №4,5.

38. Кутепов В.П., Фальк В.Н. Теория направленных отношений и логика // Изв. РАН. Теория и системы управления, 2000. №5.

39. Лобанов В.П. Разработка алгоритмов и программных средств обеспечения надежности параллельных вычислений на вычислительных комплексах // Автореф. дис. на соиск. учен, степени канд. техн. наук. М. МЭИ, 1985.

40. Марков A.A., Нагорный Н.М. Теория алгорифмов//«Наука». М., 1984.

41. Математическая логика в программировании // Сборник статей. «Мир». М.,1991.

42. Мендельсон Э. Введение в математическую логику//Москва. Наука, 1971.

43. Непейвода H.H., Свириденко ДМ. К теории синтеза программ // Труды Института математики СО АН СССР, 1982. Том 2.

44. Непейвода H.H. Семантика алгоритмических языков // «Итоги науки и техники». ВИНИТИ, серия «Теория вероятностей. Математическая статистика. Техническая кибернетика», 1983. Том 20.

45. Непомнящий В.А., Дехтярь М.И. Математическая теория программирования. Обзор зарубежных работ // ВЦ СО АН СССР. Препринт № 341. Новосибирск, 1982.

46. Нигиян С.А. Функциональные языки программирования // Программирование, 1991. №5.

47. Никитченко H.H. Композиционная семантика языков программирования // Программирование, 1982. №6.

48. Питерсон Дж. Теория сетей Петри и моделирование систем // «Мир». М., 1984.

49. Подловченко Р.И. Функциональная эквивалентность программ и ее моделирование// Программирование, 1977. №2.

50. Редько В.Н. Композиции программ и композиционное программирование // Программирование, 1978. №5.

51. Редько В.Н. Основания композиционного программирования // Программирование, 1979. №3.

52. Селегей М.Б. Разработка и реализация типизированного функционального языка параллельного программирования // Автореф. дис. на соиск. учен, степени канд. техн. наук. М. МЭИ, 1989.

53. Семантика языков программирования II Сборник статей п/ред Курочкина В.М. Мир. М.,1980.

54. Строева Т.М., Фальк В.Н. Асинхронные вычислительные сети: АВС-модель и ABC-система программирования // Кибернетика, 1981. №3.

55. Турчин В.Ф. Метаалгоритмический язык// Кибернетика, 1968. №4.

56. Турчин В.Ф. Программирование на языке РЕФАЛ (1-5) // Препринт ИПМ АН СССР, 1971. №№41,43,44,48,49.

57. Тыугу Э.Х. Решение задач на вычислительных моделях // Журн. выч. мат. и мат. Физики, 1970. №10.

58. Тыугу Э.Х. Концептуальное программирование//М. Наука, 1984.

59. Ульяновский И.И. Разработка и исследование формализованных языков функций и отношений // Автореф. дис. на соиск. учен, степени канд. техн. наук. М. МЭИ, 1988.

60. Фальк В.Н. О языке функциональных абстракций // «Цифровая вычислительная техника и программирование». Вып.№6. «Сов. Радио», 1970.

61. Фальк В.Н. Теоретические модели языков программирования и вопросы их структурной интерпретации // Автореф. дис. на соиск. учен, степени канд. техн. наук. М. МЭИ, 1977.

62. Фальк В.Н. Исследование эквивалентности схем программ средствами языка схем отношений // Программирование, 1982. №6.

63. Фальк В.Н. Теоретическая модель языка программирования высокого уровня//Программирование, 1987. №4.

64. Фальк В.Н. Языки схем отношений // Формальные модели параллельных вычислений. Новосибирск, 1988.

65. Фальк В.Н. FLOGOL входной язык системы функционально-логического программирования // Сб. науч. статей к НТК МИРЭА (ТУ). 1998.

66. Фальк В.Н. Бестиповые регулярные схемы направленных отношений // Изв. РАН. Теория и системы управления, 1998. №5.

67. Фальк В.Н., Зайцев В.И. Функциональные граф-схемы и их применение при структурном проектировании//Труды МЭИ. Вып. 121. М., 1972.

68. Хендерсон П. Функциональное программирование // М. Мир, 1983.

69. Чень Ч., flu Р. Математическая логика и автоматическое доказательство теорем // Москва. Наука. 1983.

70. Шрейдер Ю.А. Окрестностная модель языка // Труды симпозиума по применению порождающих грамматик. Тарту, 1967.

71. Apt K.R. Logic programming. Handbook of theoretical computer science // Elsevier Science Publishers. 1990.

72. Backus J. Can programming be liberated from the von Neumann style? A functional style and its algebra of programs // Comm. of the ACM, 21, 8,1978.

73. Backus J. The algebra of functional programs: function level reasoning, linear equations and extended definitions// Lect. Notes in Comp. Sci., 1981. V. 107.

74. Bellia M., Bosco P.G., Giovannetti E., Levi G., Moiso C., Palamidessi C. A two-level approach to logic and functional programming // CSELT Technical reports. Vol. XVI, 1988. №5.

75. Bellia M., Levi G. The relation between logic and functional languages: a survey // Journal of Logic Programming, 1986. №3.

76. Brachman R.J. On the Epistemological Status of Semantic Networks // Associative Networks Representation and Use of Knowledge by Computers. N.Y. Academic Press, 1979.

77. Burstall R.M., Darlington J. A transformation system for developing recursive programs//Journal of ACM, 24,1, 1977.

78. Clark K.L. Negation as Failture // Logic and data bases. N.Y. Academic Press, 1978.

79. Church A. The calculi of lambda-conversion // Princeton Univ. Press. Princeton, N.Y., 1941.80 .ColmerauerA., Picue J.F. About natural logic //Advances in data bases theory, 1. N.Y. Pltnum Press, 1981.

80. Curry H.B., Feys R. Combinatory logic//North-Holland, Amsterdam, 1958.

81. De BakkerJ.W. Recursive Procedures // Mathematisch Centrum. Tracts 24, Amsterdam, 1971.

82. De Bakker J.W., Roever W.P. A calculus for recursive program schemes // Mathematisch Centrum. Amsterdam, 1972.

83. De BakkerJ.W. The fixed point approach in semantics: theory and applications // Foundations of computer science. Mathematical Centre Tracts 63. Amsterdam, 1975.

84. Giovannetti £., Moiso C. Some aspects of the integration between logic programming and functional programming // Proc. of AIMSA'86 (North Holland), 1986.

85. Goncharov S.S., Ershov Yu.L., Sviridenco D.I. Semantic programming // Information Processing. Congr. IFIP. North Holland, 1986.

86. Greibach S.A. Theory of Program Structures: Schemes, Semantics, Verification // LNCS. V.36, 1975.

87. GrenanderU. General Pattern Theory// Oxford University Press, 1993/

88. Ehrig H., Nagl M., Rosenberg G. and Rosenfeld A. Graph Grammars and Their Application to Computer Science // Lecture Notes in Computer Science, vol. 291. Springer-Verlag, Berlin, 1987.

89. Hoare C.A.R. An axiomatic basis for computer programming // Comm. ACM, 12, 10, 1969.91 .Klop J.W. Combinatory reduction systems // PhD. Thesis. Mathematish Centrum, Amsterdam, 1980.

90. Korablin Yu.P. Deciding equivalence of functional schemes for parallel programs // Mathematical centre. Research report IW 200/82. Amsterdam, 1982.

91. Kowalski R.A. Predicate logic in programming language // Information Process-ing'74 (IFIP Congr. 74), 1974.

92. Kowalski R.A. Algorithm = Logic + Control // Comm. ACM, 22, 1979. №7.

93. Kutepov V., Falk V. Integrated tools for functional, logical and data-flow parallel programming and controlling parallel computations on computer systems // Proceedings of International Conference on parallel computing technologies. Novosibirsk, 1991.

94. Kutepov V., Falk V. Intellectual environment for computer-aided programming // Proceedings of Japan CIS symposium on knowledge based software engineering. Pereslavl-Zalesskiy, 1994.

95. Lloyd J.W. Foundation of logic programming // Berlin. Springer Verlag, 1984.

96. Manna Z., Pnueli A. Formalization of properties of functional programs // Journal of ACM, 17, 3, 1970.

97. McCarthy J. A basis for a mathematical theory of computation // Computer Programming and Formal Systems. North-Holland, Amsterdam, 1963.

98. Quillian M.R. The Teachable Language Comprehender: A simulation program and theory of language // Comm. of the ACM, 1969. Vol. 12. №8.

99. Scott D. Outline of a mathematical theory of computation // Proc. Fourth Annual Princeton Conf. on Information Sciences and Systems. Princeton Univ., 1970.

100. Scott D. Data types as lattices // SIAM Journal on Computing, 5,1976.

101. Scott D.,Strachey C. Towards a mathematical semantics for cjmputer Language // Computer and Automata. John Wiley, 1972.

102. Turner D.A. MIRANDA: a non-strict functional language with polymorphic types // Proc. of Int. Conf. of Functional Programming Languages and Architectures, LNCS 201 Springer-Verlag, 1985.

103. Tarski A. A lattice-theoretical fixpoint theorem and its applications // Pacific J. Math., 1955. №5.

104. Subrahmanyam P.A., You J.-H. FUNLOG-. A computational model integrating logic programming and functional programming // In Logic Programming: Functions, Relations and Equations. Prentice-Hall, 1986.

105. Wirth N. The programming language PASCAL // Acta Informática 1,1971.