Исследование примитивных схем программ с процедурами
https://doi.org/10.18255/1818-1015-2014-4-116-131
Аннотация
В статье рассматриваются алгебраические модели программ с процедурами, предназначенные для изучения семантических свойств программ на их схемах. Так возникают проблемы эквивалентности схем программ и проблема построения полной системы эквивалентных преобразований схем программ. Среди алгебраических моделей программ с процедурами выделены перегородчатые модели, индуцируемые моделями программ без процедур, и принадлежащие им примитивные схемы программ. Для них разрешима проблема эквивалентности. В данной статье в случае, когда индуцирующей является уравновешенная полугрупповая модель программ с левым сокращением, для определенного подкласса примитивных схем построена полная в нем система эквивалентных преобразований схем.
Об авторе
Римма Ивановна Подловченко
Московский государственный университет им. М.В. Ломоносова
Россия
проф., д-р физ.-мат. наук, 119991, Российская Федерация, Москва, Ленинские горы, д. 1
Россия
проф., д-р физ.-мат. наук, 119991, Российская Федерация, Москва, Ленинские горы, д. 1
Список литературы
1. Подловченко Р.И., Молчанов А.Э. Разрешимость эквивалентности в перегородчатых моделях программ // Моделирование и анализ информационных систем. 2014. Т. 21, №2. С. 56–70. [Podlovchenko R.I., Molchanov A.E. Equivalence Problem Solvability in Gateway Program Models // Modeling and Analysis of Information Systems. 2014. V. 21, No 2. P. 56–70 (in Russian)].
2. Подловченко Р.И. Эквивалентные преобразования в математических моделях вычислений: Учебное пособие. М.: МАКС-Пресс, 2011. 72 с. [Podlovchenko R.I. Ekvivalentnie preobrazovanija v matematicheskih modelah vichislenij: Uchebnoe posobie. M.: MAKSPress, 2011. 72 s. (in Russian)].
3. Подловченко Р.И. Полные системы эквивалентных преобразований в уравновешенных полугрупповых моделях программ с левым сокращением // Программирование. 2010. №3. С. 3–18 (Podlovchenko R.I. Complete systems of equivalent transformations in balanced semigroup models of programs with left cancellation // Programming and Computer Software. 2010. No 3. P. 125–137).
4. Подловченко Р.И., Молчанов А.Э. О теории алгебраических моделей программ с процедурами // Моделирование и анализ информационных систем. 2012. Т. 19, №5. С. 100–114 (Podlovchenko R.I., Molchanov A.E. About Algebraic Program Models with Procedures // Modeling and Analysis of Information Systems. 2012. V. 19, No 5. P. 100–114 [in Russian]).
5. Подловченко Р.И. К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ // Кибернетика и системный анализ. Киев, 2012. № 5. C. 17–24 [Podlovchenko R.I. K voprosu o polinomialnoj slozhnosti problemy ekvivalentnosti v algebraicheskih modeljah programm // Kibernetika i sistemnyj analiz. Kiev, 2012. N5. S. 17–24 (in Russian)].
6. Подловченко Р.И. Об одной методике распознавания эквивалентности в алгебраических моделях программ // Программирование. 2011. Т. 37, №6. С. 33–43. (English trans.: Podlovchenko R.I. On an equivalence checking technique for algebraic models of programs // Programming and Computer Software. 2011. V. 37, No 6. P. 292–298).
7. Ляпунов А.А. О логических схемах программ // Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. С. 46–74 [Ljapunov A.A. O logicheskih shemah programm // Problemy kibernetiki. Vyp. 1. M.: Fizmatgiz, 1958. Р. 46–74 (in Russian)].
8. Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. С. 75–127 [Janov Ju.I. O logicheskih shemah algoritmov // Problemy kibernetiki. Vyp. 1. M.: Fizmatgiz, 1958. P. 75–127 (in Russian)].
9. Глушков В.М., Летичевский А.А. Теория дискретных преобразователей // Избранные вопросы алгебры и логики: сб. статей. Новосибирск: Наука, 1973. C. 5–39 [Glushkov V.M., Letichevskij A.A. Teorija diskretnyh preobrazovatelej. Izbrannye voprosy algebry i logiki: sb. statej. Novosibirsk: Nauka, 1973. S. 5–39 (in Russian)].
10. Ершов А.П., Сабельфельд В.К. Очерки схемной теории рекурсивных программ // Трансляция и модели программ. Новосибирск, 1980. C. 23–53 [Ershov A.P., Sabelfeld V.K. Ocherki shemnoj teorii rekursivnyh programm // Transljacija i modeli programm. Novosibirsk, 1980. S. 23–53 (in Russian)].
11. Захаров В.А. Быстрые алгоритмы разрешения эквивалентности операторных программ на уравновешенных шкалах // Математические вопросы кибернетики. Bып. 7. М.: Физматлит, 1998. C. 303–324 [Zaharov V.A. Bystrye algoritmy razreshenija ekvivalentnosti operatornyh programm na uravnoveshennyh shkalah // Matematicheskie voprosy kibernetiki. Vyp. 7. M.: Fizmatlit, 1998. S. 303–324 (in Russian)].
12. Захаров В.А. Проверка эквивалентности программ при помощи двухленточных автоматов // Кибернетика и системный анализ. 2010. №4. C. 39–48 [Zaharov V.A. Proverka ekvivalentnosti programm pri pomoschi dvuhlentochnyh avtomatov // Kibernetika i sistemnyj analiz. 2010. №4. S. 39–48 (in Russian)].
13. Котов В.Е., Сабельфельд В.К. Теория схем программ. М.: Наука, 1991. 348 с. [Kotov V.E., Sabelfeld V.K. Teorija shem programm. M.: Nauka, 1991. 348 s. (in Russian)].
14. Лисовик Л.П. Металинейные рекурсивные схемы над размеченными деревьями // Программирование. 1983. №5. C. 13–22 [Lisovik L.P. Metalinejnye rekursivnye shemy nad razmechennymi derevjami // Programmirovanie. 1983. №5. S. 13–22 (in Russian)].
15. Подловченко Р.И., Попов С.В. Аппроксимируемость одних моделей другими // Вестник Московского университета. Cер. 15: Вычислительная математика и кибернетика. 2001. №2. C. 38–46 [Podlovchenko R.I., Popov S.V. Approksimiruemost odnih modelej drugimi // Vestnik Moskovskogo universiteta. Ser. 15: Vychislitelnaja matematika i kibernetika. 2001. №2. S. 38–46 (in Russian)].
16. Подловченко Р.И. От схем Янова к теории моделей программ // Математические вопросы кибернетики. М.: Наука; Физматлит, 1998. Вып. 7. C. 281–302 [Podlovchenko R.I. Ot shem Janova k teorii modelej programm // Matematicheskie voprosy kibernetiki. M.: Nauka; Fizmatlit, 1998. Vyp. 7. S. 281–302 (in Russian)].
17. Подловченко Р.И. Абстрактные программы с процедурами и конечные автоматы с магазином // Интеллектуальные системы. М.: МГУ, 1997. Т. 2, вып. 1–4. C. 275–295 [Podlovchenko R.I. Abstraktnye programmy s procedurami i konechnye avtomaty s magazinom // Intellektualnye sistemy. M.: MGU, 1997. T. 2, vyp. 1–4. S. 275–295 (in Russian)].
18. Подловченко Р.И., Долгих Б.А. Двухступенчатое моделирование программ с процедурами // Математические вопросы кибернетики. Вып. 12. М.: Физматгиз, 2003. C. 47–56 [Podlovchenko R.I., Dolgih B.A. Dvuhstupenchatoe modelirovanie programm s procedurami // Matematicheskie voprosy kibernetiki. Vyp. 12. M.: Fizmatgiz, 2003. S. 47–56 (in Russian)].
19. Подловченко Р.И. Алгебраические модели программ и автоматы // Математические вопросы кибернетики. Вып. 12. М.: Физматгиз, 2003. C. 47–56 [Podlovchenko R.I. Algebraicheskie modeli programm i avtomaty // Matematicheskie voprosy kibernetiki. Vyp. 12. M.: Fizmatgiz, 2003. S. 47–56 (in Russian)].
20. Cousot P. Constructive design of a hierarchy of semantics of transition system by abstract interpretation // Theoretical Computer Science. 2002. V. 277, №86. P. 47–103.
21. Senizergues G. The equivalence problem for deterministic pushdown automata is decidable // Lecture Notes in Computer Science. 1997. V. 1256. P. 271–281.
22. Zakharov V.A., Kuzurin N.N., Podlovchenko R.I., Scherbina V.V. Using algebraic models of programs for detecting metamorfic malwares // Труды Института Системного Программирования. Т. 12. М.: ИСП РАН, 2007. C. 77–94.
23. De Bakker J.W., Scott D.A. Theory of programs. Unpublished notes // Vienna: IBM seminar, 1969.
24. Valiant L.G. The equivalence problem for deterministic finite-turn push-down automata // Information and Control. 1974. V. 25, No. 2. P. 123–133.
25. Nielson F., Nielson H.R., Hankin C. Principles of Program Analysis // Springer, 2004.
Рецензия
Для цитирования:
Подловченко Р.И. Исследование примитивных схем программ с процедурами. Моделирование и анализ информационных систем. 2014;21(4):116-131. https://doi.org/10.18255/1818-1015-2014-4-116-131
For citation:
Podlovchenko R.I. Primitive Program Schemes with Procedures. Modeling and Analysis of Information Systems. 2014;21(4):116-131. (In Russ.) https://doi.org/10.18255/1818-1015-2014-4-116-131
Просмотров:
817
Послать статью по эл. почте 