Efficient computation of equivalent and reduced representations for stochastic automata

Networks of Stochastic Automata are an adequate formalism to describe and a nalyse complex parallel and distributed systems with respect to their funct ional behaviour and their performance. Under Markovian timing Stochastic Au tomata Networks (SANs) can be analysed efficiently exploiting a generalised tensor structure of the underlying generator matrix. Additionally, it has been shown recently that an equivalence notion can be defined for stochasti c automata such that a minimal representation for a given automaton can be defined and computed. This paper extends the definition of equivalence slig htly and describes an algorithm to compute a minimal equivalent representat ion for a stochastic automaton and to decide whether two stochastic automat a are equivalent. it is shown that the algorithm works satisfactorily even for larger state spaces and is of practical importance since Markov chains underlying SANs often can be represented by reduced Markov chains, which st ill allow the computation of exact results.