Geodesic
On the minimization problem for sequential programs
Modelirovanie i analiz informacionnyh sistem, Tome 24 (2017) no. 4, pp. 415-433

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

First-order program schemata is one of the simplest models of sequential imperative programs intended for solving verification and optimization problems. We consider the decidable relation of logical-thermal equivalence of these schemata and the problem of their size minimization while preserving logical-thermal equivalence. We prove that this problem is decidable. Further we show that the first-order program schemata supplied with logical-thermal equivalence and finite state deterministic transducers operating over substitutions are mutually translated into each other. This relationship implies that the equivalence checking problem and the minimization problem for these transducers are also decidable. In addition, on the basis of the discovered relationship, we have found a subclass of first-order program schemata such that their minimization can be performed in polynomial time by means of known techniques for minimization of finite state transducers operating over semigroups. Finally, we demonstrate that in general case the minimization problem for finite state transducers over semigroups may have several non-isomorphic solutions.
Keywords: sequential program, transducer, minimization, semigroup
Mots-clés : substitution, equivalence. 
@article{MAIS_2017_24_4_a2,
     author = {V. A. Zakharov and Sh. R. Zhailauova},
     title = {On the minimization problem for sequential programs},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {415--433},
     publisher = {mathdoc},
     volume = {24},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2017_24_4_a2/}
}
TY  - JOUR
AU  - V. A. Zakharov
AU  - Sh. R. Zhailauova
TI  - On the minimization problem for sequential programs
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2017
SP  - 415
EP  - 433
VL  - 24
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2017_24_4_a2/
LA  - ru
ID  - MAIS_2017_24_4_a2
ER  - 
%0 Journal Article
%A V. A. Zakharov
%A Sh. R. Zhailauova
%T On the minimization problem for sequential programs
%J Modelirovanie i analiz informacionnyh sistem
%D 2017
%P 415-433
%V 24
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2017_24_4_a2/
%G ru
%F MAIS_2017_24_4_a2
V. A. Zakharov; Sh. R. Zhailauova. On the minimization problem for sequential programs. Modelirovanie i analiz informacionnyh sistem, Tome 24 (2017) no. 4, pp. 415-433. http://geodesic.mathdoc.fr/item/MAIS_2017_24_4_a2/