Liveness and safeness are two key properties Petri nets should have when theyare used to model asynchronous systems. The analysis of liveness and safeness forgeneral Petri nets, though shown to be decidable by Mayr [1981], is still computa-tionally expensive (Lipton [1976]1). In this paper an hierarchical approach is taken:a class of Petri nets is recursively defined starting with simple, live and safe struc-tures, becoming progressively more complex using net transformations designed topreserve liveness and safeness.Using simple net transformations, nice nets, which are live and safe, are defined.Their behavior is too restrictive for modeling non-trivial systems, so the mutualexclusion and the repetition constructs are added to get p-p-nets. Since the use ofmutual exclusions can cause deadlock, and the use of repetitions can cause loss ofsafeness, restrictions for their use are given. Using u-p-nets as the building blocks,hierarchical nets are defined. When the mutual exclusion and repetition constructsare allowed between hierarchical nets, distributed hierarchical nets are obtained.Examples of distributed hierarchical nets used to solve synchronization problemsare given.General net transformations not preserving liveness or safeness, and a notionof duality are presented, and their effect on Petri net behavior is considered.
展开▼
