zbMATH — the first resource for mathematics

Graphs and stochastic automata networks. (English) Zbl 0862.60058
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. 217-235 (1995).
Summary: We show how some graph theoretical arguments may be used to reduce the complexity of the computation of the steady-state distribution of Markov chain. We consider the directed graph associated to a Markov chain derived from a stochastic automata network (SAN). The structural properties of the automata are used to establish new various results. First, we establish the complexity of the revolution for stochastic automata networks with a sparse matrix representation of the automata. These results are used to compare simple SAN (i.e. without functions) with methods which generate a sparse representation of Markov chains (i.e. Markovian Petri nets for instance) on some examples. Then, we show how to apply state reduction techniques on a chain associated to a SAN. We present an algorithm to solve the steady-state equations and we prove its complexity. Finally, we extend our algorithm to allow the semi-parametric analysis of stochastic automata networks.
For the entire collection see [Zbl 0940.00042].

60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
05C80 Random graphs (graph-theoretic aspects)
68Q45 Formal languages and automata