LIVENESS ANALYSIS OF SEQUENCE CONTROL SPECIFICATION DESCRIBED IN CAPACITY DESIGNATED PETRI NET USING REDUCTION.

The capacity-designated Petri net (CPN), in which each of the places can have at most a designated number of tokens, is a suitable model for describing real system behavior. Liveness analysis of CPN is important to guarantee that a system described using a CPN is deadlock free. The CPN liveness problem can be completely determined by reachability tree analysis, but it needs a large amount of calculation time in proposition to net size power. Three reduction rules are proposed which can be directly applied to the CPN model and preserve the liveness property of original net. The heuristic algorithms for realizing the reduction rules are also proposed, and an example of the reduction process using these algorithms is demonstrated.