Разрешимость эквивалентности в двухпараметрических перегородчатых моделях программ
Аннотация
Алгебраические модели программ с процедурами предназначены для изучения семантических свойств самих программ на их образах – схемах программ. Для моделей программ с процедурами, в которых оба параметра могут быть выбраны независимо, формулируются проблемы процедурной либеризации и эквивалентности. Исследуются модели программ с процедурами, строящиеся по данной модели программ без процедур. Приводятся алгоритмы решения обеих задач для таких моделей при дополнительном ограничении на разрешимость проблемы непустоты пересечения в модели программ без процедур. Показана полиномиальная сложность этих алгоритмов. В заключение предложены задачи для дальнейшего исследования.
Об авторе
Андрей Эрикович Молчанов
Московский государственный университет им. М.В. Ломоносова
Россия
аспирант, 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. Подловченко Р.И., Молчанов А.Э. Разрешимость эквивалентности в перегородчатых моделях программ // Моделирование и анализ информационных систем. 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)].
3. Подловченко Р.И. К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ // Кибернетика и системный анализ. Киев, 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)].
4. Подловченко Р.И. Об одной методике распознавания эквивалентности в алгебраических моделях программ // Программирование. 2011. №6. С. 33–43. (Podlovchenko R.I. On an equivalence checking technique for algebraic models of programs // Programming and Computer Software. 2011. No 6. P. 292–298).
5. Подловченко Р.И. Об одном классе алгебраических моделей программ, представляющем практический интерес // Программирование. 2013. №3. С. 15–28. (Podlovchenko R.I. On a Class of Algebraic Models of Programs of Practical Interest // Programming and Computer Software. 2013. No 3. P. 124–134).
6. Ляпунов А.А. О логических схемах программ // Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. C. 46–74 [Ljapunov A.A. O logicheskih shemah programm // Problemy kibernetiki. Vyp. 1. M.: Fizmatgiz, 1958. S. 46–74 (in Russian)].
7. Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. C. 75–127 [Janov Ju.I. O logicheskih shemah algoritmov // Problemy kibernetiki. Vyp. 1. M.: Fizmatgiz, 1958. S. 75–127 (in Russian)].
8. Глушков В.М., Летичевский А.А. Теория дискретных преобразователей // Избранные вопросы алгебры и логики: сб. статей. Новосибирск: Наука, 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)].
9. Ершов А.П., Сабельфельд В.К. Очерки схемной теории рекурсивных программ // Трансляция и модели программ. Новосибирск, 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)].
10. Захаров В.А. Быстрые алгоритмы разрешения эквивалентности операторных программ на уравновешенных шкалах // Математические вопросы кибернетики. Вып. 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)].
11. Захаров В.А. Проверка эквивалентности программ при помощи двухленточных автоматов // Кибернетика и системный анализ. 2010. N 4. C. 39–48 [Zaharov V.A. Proverka ekvivalentnosti programm pri pomoschi dvuhlentochnyh avtomatov // Kibernetika i sistemnyj analiz. 2010. N 4. S. 39–48 (in Russian)].
12. Котов В.Е., Сабельфельд В.К. Теория схем программ. М.: Наука, 1991. 348 с. [Kotov V.E., Sabelfeld V.K. Teorija shem programm. M.: Nauka, 1991. 348 p. (in Russian)].
13. Лисовик Л.П. Металинейные рекурсивные схемы над размеченными деревьями // Программирование. 1983. N 5. C. 13–22 [Lisovik L.P. Metalinejnye rekursivnye shemy nad razmechennymi derevjami // Programmirovanie. 1983. N 5. S. 13–22 (in Russian)].
14. Подловченко Р.И., Попов С.В. Аппроксимируемость одних моделей другими // Вестник Московского университета. Cер. 15: Вычислительная математика и кибернетика. 2001. N 2. C. 38–46 [Podlovchenko R.I., Popov S.V. Approksimiruemost odnih modelej drugimi // Vestnik Moskovskogo universiteta. Ser. 15: Vychislitelnaja matematika i kibernetika. 2001. N 2. S. 38–46 (in Russian)].
15. Подловченко Р.И. От схем Янова к теории моделей программ // Математические вопросы кибернетики. М.: Наука, Физматлит, 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)].
16. Подловченко Р.И. Абстрактные программы с процедурами и конечные автоматы с магазином // Интеллектуальные системы. М.: изд-во МГУ, 1997. Т. 2, вып. 1–4. C. 275–295 [Podlovchenko R.I. Abstraktnye programmy s procedurami i konechnye avtomaty s magazinom // Intellektualnye sistemy. M.: izd-vo MGU, 1997. T. 2, vyp. 1–4. S. 275–295 (in Russian)].
17. Подловченко Р.И., Долгих Б.А. Двухступенчатое моделирование программ с процедурами // Математические вопросы кибернетики. М.: Физматгиз, 2003. Вып. 12. С. 47–56 [Podlovchenko R.I., Dolgih B.A. Dvuhstupenchatoe modelirovanie programm s procedurami // Matematicheskie voprosy kibernetiki. M.: Fizmatgiz, 2003. Vyp. 12. S. 47–56 (in Russian)].
18. Подловченко Р.И. Алгебраические модели программ и автоматы // Математические вопросы кибернетики. М.: Физматгиз, 2003. Вып. 12. C. 47–56 (Podlovchenko R.I. Algebraicheskie modeli programm i avtomaty // Matematicheskie voprosy kibernetiki. M.: Fizmatgiz, 2003. Vyp. 12. S. 47–56 (in Russian)].
19. Cousot P. Constructive design of a hierarchy of semantics of transition system by abstract interpretation // Theoretical Computer Science. 2002. V. 277, N 86. P. 47–103.
20. Senizergues G. The equivalence problem for deterministic pushdown automata is decidable // Lectoure Notes in Computer Science. 1997. V. 1256. P. 271–281.
21. Zakharov V.A., Kuzurin N.N., Podlovchenko R.I., Scherbina V.V. Using algebraic models of programs for detecting metamorfic malwares // Труды Института Системного Программирования. М.: ИСП РАН, 2007. Т. 12. C. 77–94.
22. Подловченко Р.И. Методология построения системы эквивалентных преобразований, полной в модели вычислений, и её применение для алгебраических моделей программ // Труды семинара «Семантика, спецификация и верификация программ: теория и приложения» (Казань, 14–15 июня 2010). Казань: Отечество, 2010. C. 82–87 [Podlovchenko R.I. Metodologija postroenija sistemy ekvivalentnyh preobrazovanij, polnoj v modeli v ychislenij, i ee primenenie dlja algebraicheskih modelej programm // Trudy seminara ”Semantika, specifikacija i verifikacija programm: teorija i prilozhenija“. Kazan, 2010 (in Russian)].
23. Подловченко Р.И. Полные системы эквивалентных преобразований в уравновешенных полугрупповых моделях программ с левым сокращением // Программирование. 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).
Для цитирования:
Молчанов А.Э. Разрешимость эквивалентности в двухпараметрических перегородчатых моделях программ. Моделирование и анализ информационных систем. 2014;21(4):104-115. https://doi.org/10.18255/1818-1015-2014-4-104-115
For citation:
Molchanov A.E. Equivalence Problem Solvability in Biparametric Gateway Program Models. Modeling and Analysis of Information Systems. 2014;21(4):104-115. (In Russ.) https://doi.org/10.18255/1818-1015-2014-4-104-115
Просмотров: 411
Послать статью по эл. почте 