maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2014-4-104-115mais-102Research ArticleОригинальные статьиArticlesРазрешимость эквивалентности в двухпараметрических перегородчатых моделях программEquivalence Problem Solvability in Biparametric Gateway Program ModelsМолчановАндрей ЭриковичMolchanovA. E.

аспирант, 119991, Российская Федерация, Москва, Ленинские горы, д. 1

аспирант, GSP-1, Leninskie Gory, Moscow, 119991, Russian Federation

gurux13@gmail.comМосковский государственный университет им. М.В. ЛомоносоваРоссияLomonosov Moscow State UniversityRussian Federation201420082014214104115Copyright © Молчанов А.Э., 20142014Молчанов А.Э.Molchanov A.E.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/102

Алгебраические модели программ с процедурами предназначены для изучения семантических свойств самих программ на их образах – схемах программ. Для моделей программ с процедурами, в которых оба параметра могут быть выбраны независимо, формулируются проблемы процедурной либеризации и эквивалентности. Исследуются модели программ с процедурами, строящиеся по данной модели программ без процедур. Приводятся алгоритмы решения обеих задач для таких моделей при дополнительном ограничении на разрешимость проблемы непустоты пересечения в модели программ без процедур. Показана полиномиальная сложность этих алгоритмов. В заключение предложены задачи для дальнейшего исследования.

Algebraic program models with procedures are designed to analyze program semantic properties on their models called program schemes. Procedural liberisation problem and equivalence problem are stated for program models with procedures in which both defining parameters are chosen independently. Program models with procedures built over a given program model without procedures are investigated. Algorithms for both stated tasks are proposed for models where an additional restriction is applied: the intersection emptiness problem is solvable in the program model without procedures. Polynomial estimates for the complexity of the algorithms are shown. Some topics for further investigation are proposed.

формализация программысхема программыэквивалентность схем программперегородчатая модель программprogram formalizationprogram schemeprogram schemes equivalencegateway program modelReferencesПодловченко Р.И., Молчанов А.Э. О теории алгебраических моделей программ с процедурами // Моделирование и анализ информационных систем. 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)].Подловченко Р.И., Молчанов А.Э. О теории алгебраических моделей программ с процедурами // Моделирование и анализ информационных систем. 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)].Подловченко Р.И., Молчанов А.Э. Разрешимость эквивалентности в перегородчатых моделях программ // Моделирование и анализ информационных систем. 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)].Подловченко Р.И., Молчанов А.Э. Разрешимость эквивалентности в перегородчатых моделях программ // Моделирование и анализ информационных систем. 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)].Подловченко Р.И. К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ // Кибернетика и системный анализ. Киев, 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)].Подловченко Р.И. К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ // Кибернетика и системный анализ. Киев, 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)].Подловченко Р.И. Об одной методике распознавания эквивалентности в алгебраических моделях программ // Программирование. 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).Подловченко Р.И. Об одной методике распознавания эквивалентности в алгебраических моделях программ // Программирование. 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).Подловченко Р.И. Об одном классе алгебраических моделей программ, представляющем практический интерес // Программирование. 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).Подловченко Р.И. Об одном классе алгебраических моделей программ, представляющем практический интерес // Программирование. 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).Ляпунов А.А. О логических схемах программ // Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. C. 46–74 [Ljapunov A.A. O logicheskih shemah programm // Problemy kibernetiki. Vyp. 1. M.: Fizmatgiz, 1958. S. 46–74 (in Russian)].Ляпунов А.А. О логических схемах программ // Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. C. 46–74 [Ljapunov A.A. O logicheskih shemah programm // Problemy kibernetiki. Vyp. 1. M.: Fizmatgiz, 1958. S. 46–74 (in Russian)].Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. C. 75–127 [Janov Ju.I. O logicheskih shemah algoritmov // Problemy kibernetiki. Vyp. 1. M.: Fizmatgiz, 1958. S. 75–127 (in Russian)].Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. C. 75–127 [Janov Ju.I. O logicheskih shemah algoritmov // Problemy kibernetiki. Vyp. 1. M.: Fizmatgiz, 1958. S. 75–127 (in Russian)].Глушков В.М., Летичевский А.А. Теория дискретных преобразователей // Избранные вопросы алгебры и логики: сб. статей. Новосибирск: Наука, 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)].Глушков В.М., Летичевский А.А. Теория дискретных преобразователей // Избранные вопросы алгебры и логики: сб. статей. Новосибирск: Наука, 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)].Ершов А.П., Сабельфельд В.К. Очерки схемной теории рекурсивных программ // Трансляция и модели программ. Новосибирск, 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)].Ершов А.П., Сабельфельд В.К. Очерки схемной теории рекурсивных программ // Трансляция и модели программ. Новосибирск, 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)].Захаров В.А. Быстрые алгоритмы разрешения эквивалентности операторных программ на уравновешенных шкалах // Математические вопросы кибернетики. Вып. 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)].Захаров В.А. Быстрые алгоритмы разрешения эквивалентности операторных программ на уравновешенных шкалах // Математические вопросы кибернетики. Вып. 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)].Захаров В.А. Проверка эквивалентности программ при помощи двухленточных автоматов // Кибернетика и системный анализ. 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)].Захаров В.А. Проверка эквивалентности программ при помощи двухленточных автоматов // Кибернетика и системный анализ. 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)].Котов В.Е., Сабельфельд В.К. Теория схем программ. М.: Наука, 1991. 348 с. [Kotov V.E., Sabelfeld V.K. Teorija shem programm. M.: Nauka, 1991. 348 p. (in Russian)].Котов В.Е., Сабельфельд В.К. Теория схем программ. М.: Наука, 1991. 348 с. [Kotov V.E., Sabelfeld V.K. Teorija shem programm. M.: Nauka, 1991. 348 p. (in Russian)].Лисовик Л.П. Металинейные рекурсивные схемы над размеченными деревьями // Программирование. 1983. N 5. C. 13–22 [Lisovik L.P. Metalinejnye rekursivnye shemy nad razmechennymi derevjami // Programmirovanie. 1983. N 5. S. 13–22 (in Russian)].Лисовик Л.П. Металинейные рекурсивные схемы над размеченными деревьями // Программирование. 1983. N 5. C. 13–22 [Lisovik L.P. Metalinejnye rekursivnye shemy nad razmechennymi derevjami // Programmirovanie. 1983. N 5. S. 13–22 (in Russian)].Подловченко Р.И., Попов С.В. Аппроксимируемость одних моделей другими // Вестник Московского университета. 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)].Подловченко Р.И., Попов С.В. Аппроксимируемость одних моделей другими // Вестник Московского университета. 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)].Подловченко Р.И. От схем Янова к теории моделей программ // Математические вопросы кибернетики. М.: Наука, Физматлит, 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)].Подловченко Р.И. От схем Янова к теории моделей программ // Математические вопросы кибернетики. М.: Наука, Физматлит, 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)].Подловченко Р.И. Абстрактные программы с процедурами и конечные автоматы с магазином // Интеллектуальные системы. М.: изд-во МГУ, 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)].Подловченко Р.И. Абстрактные программы с процедурами и конечные автоматы с магазином // Интеллектуальные системы. М.: изд-во МГУ, 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)].Подловченко Р.И., Долгих Б.А. Двухступенчатое моделирование программ с процедурами // Математические вопросы кибернетики. М.: Физматгиз, 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)].Подловченко Р.И., Долгих Б.А. Двухступенчатое моделирование программ с процедурами // Математические вопросы кибернетики. М.: Физматгиз, 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)].Подловченко Р.И. Алгебраические модели программ и автоматы // Математические вопросы кибернетики. М.: Физматгиз, 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)].Подловченко Р.И. Алгебраические модели программ и автоматы // Математические вопросы кибернетики. М.: Физматгиз, 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)].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.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.Senizergues G. The equivalence problem for deterministic pushdown automata is decidable // Lectoure Notes in Computer Science. 1997. V. 1256. P. 271–281.Senizergues G. The equivalence problem for deterministic pushdown automata is decidable // Lectoure Notes in Computer Science. 1997. V. 1256. P. 271–281.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.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.Подловченко Р.И. Методология построения системы эквивалентных преобразований, полной в модели вычислений, и её применение для алгебраических моделей программ // Труды семинара «Семантика, спецификация и верификация программ: теория и приложения» (Казань, 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)].Подловченко Р.И. Методология построения системы эквивалентных преобразований, полной в модели вычислений, и её применение для алгебраических моделей программ // Труды семинара «Семантика, спецификация и верификация программ: теория и приложения» (Казань, 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)].Подловченко Р.И. Полные системы эквивалентных преобразований в уравновешенных полугрупповых моделях программ с левым сокращением // Программирование. 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).Подловченко Р.И. Полные системы эквивалентных преобразований в уравновешенных полугрупповых моделях программ с левым сокращением // Программирование. 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).

The authors declare that there are no conflicts of interest present.