Geodesic
Equivalence Problem Solvability in Gateway Program Models
Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 2, pp. 56-70.

Voir la notice de l'article provenant de la source Math-Net.Ru

Algebraic program models with procedures are designed to analyze program semantic properties on their models called program schemes. Liberisation and equivalence problems are stated for program models with procedures. A subclass of program models with procedures called special gateway models is investigated. A better complexity algorithm for the liberisation in such models is proposed. Primitive program schemes are defined as a subclass of special gateway models. It is shown that the equivalence problem in such models is decidable if the equivalence problem is decidable in special program models without procedures. For some cases of decidability the complexity is evaluated.
Keywords: program formalization, program scheme, program schemes equivalence, gateway program model. 
@article{MAIS_2014_21_2_a5,
     author = {R. I. Podlovchenko and A. E. Molchanov},
     title = {Equivalence {Problem} {Solvability} in {Gateway} {Program} {Models}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {56--70},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2014_21_2_a5/}
}
TY  - JOUR
AU  - R. I. Podlovchenko
AU  - A. E. Molchanov
TI  - Equivalence Problem Solvability in Gateway Program Models
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2014
SP  - 56
EP  - 70
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2014_21_2_a5/
LA  - ru
ID  - MAIS_2014_21_2_a5
ER  - 
%0 Journal Article
%A R. I. Podlovchenko
%A A. E. Molchanov
%T Equivalence Problem Solvability in Gateway Program Models
%J Modelirovanie i analiz informacionnyh sistem
%D 2014
%P 56-70
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2014_21_2_a5/
%G ru
%F MAIS_2014_21_2_a5
R. I. Podlovchenko; A. E. Molchanov. Equivalence Problem Solvability in Gateway Program Models. Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 2, pp. 56-70. http://geodesic.mathdoc.fr/item/MAIS_2014_21_2_a5/

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

[2] 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) | Zbl

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

[4] R. I. Podlovchenko, “On a class of algebraic models of programs of practical interest”, Programming and Computer Software, 39:3 (2013), 124–134 | DOI | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[20] 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, ISP RAN, M., 2007, 77–94