Transformations of petri nets for system analysis

Abstract

In this thesis, three transformation methods of Petri nets to simplify the analysis of Petri net modeled systems are proposed. In the literature, mostly proposed reachability graph (or the set of all the reachable markings) of the corresponding Petri net for analyzing some characteristics of a system such as safeness, deadlock-freeness and liveness etc. However, constructing the reachability graph of a complicated Petri net requires much time and a large state space. The complexity is known to be at least exponential and may not even be decidable [Lipt76]. So the problem of keeping the exponential growth of the state space of complex Petri net under control is an important issue as this growth may impair the analysis of realistic systems. To resolve the problem, many researchers have proposed abstraction and refinement methods of the net which are based on the characteristics of the subnet. But their methods are much more fitted to the stepwise refinement of the net since the safeness (boundedness) of the net must be checked first [Suzu83] [Vale79]. In this thesis, at first, a transformation (abstraction) method for simplification of Petri nets which is an extension of Suzuki``s work (abstraction of k-well behaved module) is proposed. Convertible subnet (CSN) is defined so that the boundedness of the original net is not to be checked. Furthermore, some transitions in the CSN may have output arcs to the places outside the CSN. This implies that the abstracted module may have interaction outside the module not through the entry or exit points. A complicated Petri net is transformed into a simler one whih a smaller state space by hierarchically replacing a CSN with the corresponing decision net. It is shown that the properties (liveness, boundness etc.) of the original net is not changed during the transformation and an illustrative example of the abstraction is given which is a simple CPU model. Also to analyze the performance of a system modeled by a timed Petri...