zbMATH — the first resource for mathematics

Equivalence relations for stochastic automata networks. (English) Zbl 0861.68004
Stewart, William J. (ed.), Computations with Markov chains. Proceedings of the 2nd international workshop on the numerical solution of Markov chains, Raleigh, NC, USA, January 16–18, 1995. Boston, MA: Kluwer Academic Publishers. 197-215 (1995).
Summary: Stochastic Automata Networks (SANs) are an efficient means to describe and analyze parallel systems under Markovian assumptions. The main advantage of SANs is the possibility to describe and analyze a complex parallel system in a compositional way such that the transition matrix of the Markov chain underlying the complete SAN can be described in a compositional way using only small matrices specifying single automata and combine these matrices by means of tenser operations. This approach allows, up to a certain extent, the handling of the state space explosion resulting from complex Markov models. In this paper, equivalence relations for stochastic automata are introduced such that an automaton in a network can be substituted by an equivalent and usually smaller automaton without affecting the results of an analysis. We consider equivalence according to stationary and transient analysis of SANs.
For the entire collection see [Zbl 0940.00042].

68M10 Network design and communication in computer systems
68Q45 Formal languages and automata