This article is cited in 2 scientific papers (total in 2 papers)
On the minimization of finite state transducers over semigroups
V. A. Zakharov, G. G. Temerbekova
Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics, GSP-1, 1-52 Leninskiye Gory, Moscow 119991, Russia
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.
reactive system, transducer, semigroup, minimization, equivalence checking.
|Russian Foundation for Basic Research
|This work is supported by the Basic Research Program at the National Research University Higher School of Economics
in 2016 and by RFBR grants №16-01-00546.
PDF file (618 kB)
V. A. Zakharov, G. G. Temerbekova, “On the minimization of finite state transducers over semigroups”, Model. Anal. Inform. Sist., 23:6 (2016), 741–753
Citation in format AMSBIB
\by V.~A.~Zakharov, G.~G.~Temerbekova
\paper On the minimization of finite state transducers over semigroups
\jour Model. Anal. Inform. Sist.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
V. A. Zakharov, Sh. R. Zhailauova, “O zadache minimizatsii posledovatelnykh programm”, Model. i analiz inform. sistem, 24:4 (2017), 415–433
V. A. Zakharov, A. R. Gnatenko, “O vyrazitelnykh vozmozhnostyakh nekotorykh rasshirenii lineinoi temporalnoi logiki”, Model. i analiz inform. sistem, 25:5 (2018), 506–524
|Number of views:|