Abstract: The theory of probabilistic automata is still evolving discipline of theory of information. As in classical theory of automata, it might be a base for computations, can be exploited in design and verification of circuits and algorithms, in lexical analyzers in compilers computers in future. Minimization of any type of automata gives always saving in resources and time, and is important problem that has been analyzed for almost sixty years. Different types of automata are used for modeling systems or machines with finite number of states. In this article we show few specific type of probabilistic automata, especially 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:

METHOD AND ALGORITHM FOR MINIMIZATION OF PROBABILISTIC AUTOMATA

Olga Siedlecka

http://foibg.com/ijita/vol16/IJITA16-1-p04.pdf