Reduction and Refinement by Algebraic Operations for Petri Net Transformation

Petri net (PN) transformation is a method for converting a net from one structure to another. The existing approaches are net content dependent, i.e., all elements of the right- and left-hand-side nets or the operand nets participate in matching and related operations during transformation. They incur high computational complexity and difficulty to predict the transformation results. Reduction and refinement as two kinds of elementary net transformation have not been brought into a unified framework of net transformation approaches. In addition, the criteria for steering net transformation have not been separated from the transformation manipulations in the existing reduction and refinement methods. To solve these problems, this work proposes a net algebraic system for the general transformation of nets. It possesses node operation, block operation, and basic place- and transition-interfaced net operation algebras. Net-content-independent transformation, in which only the location and operation of the operand nets´ interfaces are involved, can be achieved in a net algebraic way. Furthermore, by composing several operations, new operations for reduction and refinement are defined within a unified net transformation framework in which they are independent of the specific transformation criteria. Subsequently, the equivalence between the original and transformed nets with respect to PN properties as the criterion is investigated and proved when several newly proposed subnet structures are used as operands. Finally, the algebraic reduction operation is applied to analyze a complicated PN model of a mail sorting system.