Primitive Program Schemes with Procedures
https://doi.org/10.18255/1818-1015-2014-4-116-131
Abstract
The paper considers algebraic program models with procedures designed to analyze program semantic properties based on program schemes. This leads to the problem of program scheme equivalence and the problem of constructing a complete system of equivalent program scheme transformations. Among algebraic program models with procedures, we focus on gateway models induced by program models without procedures and primitive program schemes belonging to these gateway models. The equivalence problem is decidable for these schemes. In the case where the inducer is a special type of program model without procedures, we construct a complete system of equivalent scheme transformations for a particular subclass of primitive program schemes.
About the Author
R. I. Podlovchenko
Lomonosov Moscow State University
Russian Federation
проф., д-р физ.-мат. наук, GSP-1, Leninskie Gory, Moscow, 119991, Russian Federation
Russian Federation
проф., д-р физ.-мат. наук, GSP-1, Leninskie Gory, Moscow, 119991, Russian Federation
References
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.
Review
For citations:
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
Views:
831
Email this article 