Equivalence Problem Solvability in Gateway Program Models
https://doi.org/10.18255/1818-1015-2014-2-56-70
Abstract
Algebraic program models with procedures are designed to analyze program semantic properties on their models called program schemes. Liberisation and equivalence problems are stated for program models with procedures. A subclass of program models with procedures called special gateway models is investigated. A better complexity algorithm for the liberisation in such models is proposed. Primitive program schemes are defined as a subclass of special gateway models. It is shown that the equivalence problem in such models is decidable if the equivalence problem is decidable in special program models without procedures. For some cases of decidability the complexity is evaluated.
About the Authors
R. I. Podlovchenko
Lomonosov Moscow State University
Russian Federation
Russian Federation
д-р физ.-мат. наук, проф., ведущий научный сотрудник НИВЦ,
GSP-1, Leninskie Gory, Moscow, 119991, Russian Federation
A. E. Molchanov
Lomonosov Moscow State University
Russian Federation
Russian Federation
аспирант ф-та ВМК,
GSP-1, Leninskie Gory, Moscow, 119991, Russian Federation
References
1. Подловченко Р.И., Молчанов А.Э. О теории алгебраических моделей программ с процедурами // Моделирование и анализ информационных систем. 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)].
2. Подловченко Р.И. К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ // Кибернетика и системный анализ. Киев, 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. No 5. P. 17–24 (in Russian)].
3. Подловченко Р.И. Об одной методике распознавания эквивалентности в алгебраических моделях программ // Программирование. 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].
4. Подловченко Р.И. Об одном классе алгебраических моделей программ, представляющем практический интерес // Программирование. 2013. №3. С. 15–28. [English trans.: Podlovchenko R.I. On a class of algebraic models of programs of practical interest // Programming and Computer Software. 2013. V. 39, No 3. P. 124–134].
5. Ляпунов А.А. О логических схемах программ // Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. С. 46–74 [Ljapunov A.A. O logicheskih shemah programm // Problemy kibernetiki. Vyp. 1. M.: Fizmatgiz, 1958. Р. 46–74 (in Russian)].
6. Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. С. 75–127 [Janov Ju.I. O logicheskih shemah algoritmov // Problemy kibernetiki. Vyp. 1. M.: Fizmatgiz, 1958. P. 75–127 (in Russian)].
7. Глушков В.М., Летичевский А.А. Теория дискретных преобразователей // Избранные вопросы алгебры и логики: сб. статей. Новосибирск: Наука, 1973. C. 5–39 [Glushkov V.M., Letichevskij A.A. Teorija diskretnyh preobrazovatelej. Izbrannye voprosy algebry i logiki: sb. statej. Novosibirsk: Nauka, 1973. P. 5–39 (in Russian)].
8. Ершов А.П., Сабельфельд В.К. Очерки схемной теории рекурсивных программ // Трансляция и модели программ. Новосибирск, 1980. C. 23–53 [Ershov A.P., Sabelfeld V.K. Ocherki shemnoj teorii rekursivnyh programm // Transljacija i modeli programm. Novosibirsk, 1980. P. 23–53 (in Russian)].
9. Захаров В.А. Быстрые алгоритмы разрешения эквивалентности операторных программ на уравновешенных шкалах // Математические вопросы кибернетики. 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. P. 303–324 (in Russian)].
10. Захаров В.А. Проверка эквивалентности программ при помощи двухленточных автоматов // Кибернетика и системный анализ. 2010. №4. C. 39–48 [Zaharov V.A. Proverka ekvivalentnosti programm pri pomoschi dvuhlentochnyh avtomatov // Kibernetika i sistemnyj analiz. 2010. №4. P. 39–48 (in Russian)].
11. Котов В.Е., Сабельфельд В.К. Теория схем программ. М.: Наука, 1991. 348 с. [Kotov V.E., Sabelfeld V.K. Teorija shem programm. M.: Nauka, 1991. 348 p. (in Russian)].
12. Лисовик Л.П. Металинейные рекурсивные схемы над размеченными деревьями // Программирование. 1983. №5. C. 13–22 [Lisovik L.P. Metalinejnye rekursivnye shemy nad razmechennymi derevjami // Programmirovanie. 1983. №5. P. 13–22 (in Russian)].
13. Подловченко Р.И., Попов С.В. Аппроксимируемость одних моделей другими // Вестник Московского университета. 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. P. 38–46 (in Russian)].
14. Подловченко Р.И. От схем Янова к теории моделей программ // Математические вопросы кибернетики. М.: Наука; Физматлит, 1998. Вып. 7. C. 281–302 [Podlovchenko R.I. Ot shem Janova k teorii modelej programm // Matematicheskie voprosy kibernetiki. M.: Nauka; Fizmatlit, 1998. Vyp. 7. P. 281–302 (in Russian)].
15. Подловченко Р.И. Абстрактные программы с процедурами и конечные автоматы с магазином // Интеллектуальные системы. М.: МГУ, 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. P. 275–295 (in Russian)].
16. Подловченко Р.И., Долгих Б.А. Двухступенчатое моделирование программ с процедурами // Математические вопросы кибернетики. Вып. 12. М.: Физматгиз, 2003. C. 47–56 [Podlovchenko R.I., Dolgih B.A. Dvuhstupenchatoe modelirovanie programm s procedurami // Matematicheskie voprosy kibernetiki. Vyp. 12. M.: Fizmatgiz, 2003. P. 47–56 (in Russian)].
17. Подловченко Р.И. Алгебраические модели программ и автоматы // Математические вопросы кибернетики. Вып. 12. М.: Физматгиз, 2003. C. 47–56 [Podlovchenko R.I. Algebraicheskie modeli programm i avtomaty // Matematicheskie voprosy kibernetiki. Vyp. 12. M.: Fizmatgiz, 2003, P. 47–56 (in Russian)].
18. 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.
19. Senizergues G. The equivalence problem for deterministic pushdown automata is decidable // Lectoure Notes in Computer Science. 1997. V. 1256. P. 271–281.
20. 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.
Review
For citations:
Podlovchenko R.I., Molchanov A.E. Equivalence Problem Solvability in Gateway Program Models. Modeling and Analysis of Information Systems. 2014;21(2):56-70. (In Russ.) https://doi.org/10.18255/1818-1015-2014-2-56-70
Views:
774
Email this article 