Automated construction of compound Markov chains from generalized stochastic high-level Petri nets

A new type of Petri nets called generalized stochastic high-level Petri nets (GSHLPNs), combining the quantities of GSPNs and SHLPNs, is presented. The automated construction of compound continuous-time Markov chains (CTMCs) from GSHLPNs is also considered. A formalism for the description of compound markings allowing a symbolic firing of the net to obtain a compound CTMC with correct state group is derived. The construction of the compound CTMC requires an algorithm to test the equivalence of compound markings. I tis shown that, in the general case and for bounded number of rotation groups, the problem is polynomially equivalent to graph isomorphism, a problem whose classification in the NP world is currently open