Equivalence Problem Solvability in Biparametric Gateway Program Models

A. E. Molchanov

Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 4, pp. 104-115.

Résumé

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.

Détail

Keywords: program formalization, program scheme, program schemes equivalence, gateway program model.

Bibliographie

[1] Podlovchenko R. I., Molchanov A. E., “About Algebraic Program Models with Procedures”, Modeling and Analysis of Information Systems, 19:5 (2012), 100–114 (in Russian) | MR

[2] Podlovchenko R. I., Molchanov A. E., “Equivalence Problem Solvability in Gateway Program Models”, Modeling and Analysis of Information Systems, 21:2 (2014), 56–70 (in Russian)

[3] Podlovchenko R. I., “K voprosu o polinomialnoj slozhnosti problemy ekvivalentnosti v algebraicheskih modeljah programm”, Kibernetika i sistemnyj analiz, 2012, no. 5, 17–24 (in Russian) | MR | Zbl

[4] R. I. Podlovchenko, “On an equivalence checking technique for algebraic models of programs”, Programming and Computer Software, 2011, no. 6, 292–298 | DOI | MR | Zbl

[5] R. I. Podlovchenko, “On a Class of Algebraic Models of Programs of Practical Interest”, Programming and Computer Software, 2013, no. 3, 124–134 | DOI | MR | Zbl

[6] Ljapunov A. A., “O logicheskih shemah programm”, Problemy kibernetiki, 1, Fizmatgiz, M., 1958, 46–74 (in Russian)

[7] Janov Ju. I., “O logicheskih shemah algoritmov”, Problemy kibernetiki, 1, Fizmatgiz, M., 1958, 75–127 (in Russian)

[8] Glushkov V. M., Letichevskij A. A., “Teorija diskretnyh preobrazovatelej”, Izbrannye voprosy algebry i logiki, sb. statej, Nauka, Novosibirsk, 1973, 5–39 (in Russian)

[9] Ershov A. P., Sabelfeld V. K., “Ocherki shemnoj teorii rekursivnyh programm”, Transljacija i modeli programm, Novosibirsk, 1980, 23–53 (in Russian)

[10] Zaharov V. A., “Bystrye algoritmy razreshenija ekvivalentnosti operatornyh programm na uravnoveshennyh shkalah”, Matematicheskie voprosy kibernetiki, 7, Fizmatlit, M., 1998, 303–324 (in Russian)

[11] Zaharov V. A., “Proverka ekvivalentnosti programm pri pomoschi dvuhlentochnyh avtomatov”, Kibernetika i sistemnyj analiz, 2010, no. 4, 39–48 (in Russian) | Zbl

[12] Kotov V. E., Sabelfeld V. K., Teorija shem programm, Nauka, M., 1991, 348 pp. (in Russian) | MR

[13] Lisovik L. P., “Metalinejnye rekursivnye shemy nad razmechennymi derevjami”, Programmirovanie, 1983, no. 5, 13–22 (in Russian) | MR | Zbl

[14] Podlovchenko R. I., Popov S. V., “Approksimiruemost odnih modelej drugimi”, Vestnik Moskovskogo universiteta. Ser. 15: Vychislitelnaja matematika i kibernetika, 2001, no. 2, 38–46 (in Russian) | MR | Zbl

[15] Podlovchenko R. I., “Ot shem Janova k teorii modelej programm”, Matematicheskie voprosy kibernetiki, 7, Nauka. Fizmatlit, M., 1998, 281–302 (in Russian) | MR

[16] Podlovchenko R. I., “Abstraktnye programmy s procedurami i konechnye avtomaty s magazinom”, Intellektualnye sistemy, 2:1–4 (1997), 275–295 (in Russian)

[17] Podlovchenko R. I., Dolgih B. A., “Dvuhstupenchatoe modelirovanie programm s procedurami”, Matematicheskie voprosy kibernetiki, 12, Fizmatgiz, M., 2003, 47–56 (in Russian)

[18] Podlovchenko R. I., “Algebraicheskie modeli programm i avtomaty”, Matematicheskie voprosy kibernetiki, 12, Fizmatgiz, M., 2003, 47–56 (in Russian)

[19] P. Cousot, “Constructive design of a hierarchy of semantics of transition system by abstract interpretation”, Theoretical Computer Science, 277:86 (2002), 47–103 | DOI | MR | Zbl

[20] G. Senizergues, “The equivalence problem for deterministic pushdown automata is decidable”, Lecture Notes in Computer Science, 1256, 1997, 271–281 | MR

[21] V. A. Zakharov, N. N. Kuzurin, R. I. Podlovchenko, V. V. Scherbina, “Using algebraic models of programs for detecting metamorfic malwares”, Trudy Instituta Sistemnogo Programmirovaniya, 12 (2007), 77–94

[22] 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] R. I. Podlovchenko, “Complete systems of equivalent transformations in balanced semigroup models of programs with left cancellation”, Programming and Computer Software, 2010, no. 3, 125–137 | DOI | MR | Zbl