In: Proc. High Performance Computing (HPC'2000); 2000 Advanced Simulation Technologies Conference, 16-20 April 2000, Washington, DC, pages 345-356. 2000.
Abstract: Petri nets and Markovian Petri nets are excellent tools for logic and performability system modeling. However, the size of the underlying reachability set is a major limitation in practice. One approach gaining attention among researchers is the use of structured representations, which requires to decompose the net into, or compose net from, subnets. This paper surveys the state-of-the-art in advanced techniques for storing the reachability set and the transition rate matrix, with particular attention to the use of decision diagrams, Kronecker representations, and their interplay. The conclusion is, that in most practical applications, it is now possible to generate and store enormous reachability sets for logical analysis, while the size of the probability vector being sought is the main limitation when performing the exact solution of the underlying Markov chain.
Keywords: Kronecker algebra, Markov chains, decision diagrams, performance analysis, stochastic Petri nets, structured models.