Разрешимость эквивалентности в перегородчатых моделях программ
https://doi.org/10.18255/1818-1015-2014-2-56-70
Аннотация
Алгебраические модели программ с процедурами предназначены для изучения семантических свойств самих программ на их образах–схемах программ. Для моделей программ с процедурами формулируются проблемы либеризации и эквивалентности. Рассматривается подкласс моделей программ с процедурами – специальные перегородчатые модели. Для таких моделей программ улучшена оценка сложности алгоритма, решающего проблему либеризации. Введено понятие примитивных схем программ как подкласса специальных перегородчатых. Для них установлена разрешимость проблемы эквивалентности при разрешимости проблемы эквивалентности в специального вида моделях программ без процедур. Для некоторых случаев разрешимости проблемы эквивалентности приведены оценки сложности.
Об авторах
Римма Ивановна Подловченко
Московский государственный университет им. М.В. Ломоносова
Россия
Россия
д-р физ.-мат. наук, проф., ведущий научный сотрудник НИВЦ,
119991, Российская Федерация, Москва, Ленинские горы, д. 1
Андрей Эрикович Молчанов
Московский государственный университет им. М.В. Ломоносова
Россия
Россия
аспирант ф-та ВМК,
119991, Российская Федерация, Москва, Ленинские горы, д. 1
Список литературы
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.
Рецензия
Для цитирования:
Подловченко Р.И., Молчанов А.Э. Разрешимость эквивалентности в перегородчатых моделях программ. Моделирование и анализ информационных систем. 2014;21(2):56-70. https://doi.org/10.18255/1818-1015-2014-2-56-70
For citation:
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
Просмотров:
775
Послать статью по эл. почте 