Minimization of Reactive Probabilistic Automata


Autoria(s): Siedlecka, Olga
Data(s)

07/04/2010

07/04/2010

2008

Resumo

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.

Identificador

1313-0455

http://hdl.handle.net/10525/1007

Idioma(s)

en

Publicador

Institute of Information Theories and Applications FOI ITHEA

Palavras-Chave #Theory of Computation #Minimization Algorithm #Reactive Probabilistic Automata #Equivalence of States of Automata #Bisimulation Relation
Tipo

Article