EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, VOL.148, NO.2, PP.436-451, 2003.

TITLE: Lumpable Continuous-Time Stochastic Automata Networks

AUTHORS: Oleg Gusak, Tugrul Dayar, and Jean-Michel Fourneau 

ABSTRACT: The generator matrix of a continuous-time stochastic automata
network (SAN) is a sum of tensor products of smaller matrices, which may 
have entries that are functions of the global state space. This paper 
specifies easy to check conditions for a class of ordinarily lumpable 
partitionings of the generator of a continuous-time SAN in which 
aggregation is performed automaton by automaton. When there exists a 
lumpable partitioning induced by the tensor representation of the 
generator, it is shown that an efficient aggregation-iterative 
disaggregation algorithm may be employed to compute the steady state 
distribution. The results of experiments with two SAN models show that 
the proposed algorithm performs better than the highly competitive block 
Gauss-Seidel in terms of both the number of iterations and the time to 
converge to the solution.

KEY WORDS: Markov processes; Stochastic automata networks; Ordinary
lumpability; Aggregation with iterative disaggregation.