Primitive Program Schemes with Procedures

R. I. Podlovchenko

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

Résumé

The paper considers algebraic program models with procedures designed to analyze program semantic properties based on program schemes. This leads to the problem of program scheme equivalence and the problem of constructing a complete system of equivalent program scheme transformations. Among algebraic program models with procedures, we focus on gateway models induced by program models without procedures and primitive program schemes belonging to these gateway models. The equivalence problem is decidable for these schemes. In the case where the inducer is a special type of program model without procedures, we construct a complete system of equivalent scheme transformations for a particular subclass of primitive program schemes.

Détail

Keywords: algebraic program model, program schemes equivalent transformations.

Bibliographie

[1] 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)

[2] Podlovchenko R. I., Ekvivalentnie preobrazovanija v matematicheskih modelah vichislenij, Text book, MAKS-Press, M., 2011, 72 pp. (in Russian)

[3] 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

[4] 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

[5] 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

[6] R. I. Podlovchenko, “Ob odnoi metodike raspoznavaniya ekvivalentnosti v algebraicheskikh modelyakh programm”, Programmirovanie, 37:6 (2011), 33–43 | MR

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

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

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

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

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

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

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

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

[15] 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

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

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

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

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

[20] 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

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

[22] 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

[23] J. W. De Bakker, D. A. Scott, Theory of programs, IBM seminar. Unpublished notes, Vienna, 1969

[24] L. G. Valiant, “The equivalence problem for deterministic finite-turn push-down automata”, Information and Control, 25:2 (1974), 123–133 | DOI | MR | Zbl

[25] F. Nielson, H. R. Nielson, C. Hankin, Principles of Program Analysis, Springer, 2004