Abstract: The problem of finite automata minimization is important for software and hardware designing. Different
types of automata are used for modeling systems or machines with finite number of states. The limitation of
number of states gives savings in resources and time. In this article we show specific type of probabilistic
automata: the reactive probabilistic finite automata with accepting states (in brief the reactive probabilistic
automata), and definitions of languages accepted by it. We present definition of bisimulation relation for
automata's states and define relation of indistinguishableness of automata states, on base of which we could
effectuate automata minimization. Next we present detailed algorithm reactive probabilistic automata’s
minimization with determination of its complexity and analyse example solved with help of this algorithm.

Keywords: minimization algorithm, reactive probabilistic automata, equivalence of states of automata,
bisimulation relation.

ACM Classification Keywords: F. Theory of Computation, F.1 Computation by Abstract Devices, F.1.1 Models
of Computation, Automata; F.4 Mathematical logic and formal languages, F.4.3 Formal Languages

Link:

MINIMIZATION OF REACTIVE PROBABILISTIC AUTOMATA

Olga Siedlecka

http://www.foibg.com/ibs_isc/ibs-01/IBS-01-p10.pdf