Geodesic
On the minimization of finite state transducers over semigroups
Modelirovanie i analiz informacionnyh sistem, Tome 23 (2016) no. 6, pp. 741-753

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

Finite state transducers over semigroups are regarded as a formal model of sequential reactive programs that operate in the interaction with the environment. At receiving a piece of data a program performs a sequence of actions and displays the current result. Such programs usually arise at implementation of computer drivers, on-line algorithms, control procedures. In many cases verification of such programs can be reduced to minimization and equivalence checking problems for finite state transducers. Minimization of a transducer over a semigroup is performed in three stages. At first the greatest common left-divisors are computed for all states of the transducer, next the transducer is brought to a reduced form by pulling all such divisors “upstream”, and finally a minimization algorithm for finite state automata is applied to the reduced transducer.
Keywords: reactive system, transducer, semigroup, minimization, equivalence checking. 
@article{MAIS_2016_23_6_a5,
     author = {V. A. Zakharov and G. G. Temerbekova},
     title = {On the minimization of finite state transducers over semigroups},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {741--753},
     publisher = {mathdoc},
     volume = {23},
     number = {6},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2016_23_6_a5/}
}
TY  - JOUR
AU  - V. A. Zakharov
AU  - G. G. Temerbekova
TI  - On the minimization of finite state transducers over semigroups
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2016
SP  - 741
EP  - 753
VL  - 23
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2016_23_6_a5/
LA  - ru
ID  - MAIS_2016_23_6_a5
ER  - 
%0 Journal Article
%A V. A. Zakharov
%A G. G. Temerbekova
%T On the minimization of finite state transducers over semigroups
%J Modelirovanie i analiz informacionnyh sistem
%D 2016
%P 741-753
%V 23
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2016_23_6_a5/
%G ru
%F MAIS_2016_23_6_a5
V. A. Zakharov; G. G. Temerbekova. On the minimization of finite state transducers over semigroups. Modelirovanie i analiz informacionnyh sistem, Tome 23 (2016) no. 6, pp. 741-753. http://geodesic.mathdoc.fr/item/MAIS_2016_23_6_a5/