In: J.-M. Colom, M. Koutny (Eds.), Newcastle upon Tyne, UK: Proc. of 22nd International Conf. on Applications and Theory of Petri Nets 2001 (ICATPN 2001), pages 164-183. Lecture Notes in Computer Science 2075, edited by G. Goos, J. Hartmanis and J. van Leuwen, Springer, June 2001.
Abstract: The model of Stochastic Petri nets (SPN) with a product form solution (-net) is a class of nets for which there is an analytic expression of the steady state probabilities w.r.t. markings, as for product form queueing networks w.r.t. queue lengths. In this paper, we prove new important properties of this kind of nets. First we provide a polynomial time (w.r.t. the size of the net structure) algorithm to check whether a SPN is a -net. Then, we give a purely structural characterization of SPN for which a product form solution exists regardless the particular values of probabilistic parameters of the SPN. We call such nets -nets. We also present untimed properties of -nets and -nets such like liveness, reachability, deadlock freeness and characterization of reachable markings. The complexity of the reachability and the liveness problems is also addressed for -nets and -nets. These results complement previous studies on these classes of nets and improve the applicability of Product Form solutions.