|
This article is cited in 3 scientific papers (total in 3 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
Abstract:
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.
Received: 15.08.2016
Citation:
V. A. Zakharov, G. G. Temerbekova, “On the minimization of finite state transducers over semigroups”, Model. Anal. Inform. Sist., 23:6 (2016), 741–753
Linking options:
https://www.mathnet.ru/eng/mais537 https://www.mathnet.ru/eng/mais/v23/i6/p741
|
Statistics & downloads: |
Abstract page: | 336 | Full-text PDF : | 101 | References: | 40 |
|