TY - JOUR
T1 - Reduction and refinement by algebraic operations for Petri net transformation
AU - Li, Jun
AU - Zhou, Meng Chu
AU - Dai, Xianzhong
N1 - Funding Information:
Manuscript received November 2, 2010; revised August 2, 2011; accepted October 20, 2011. Date of publication March 13, 2012; date of current version August 15, 2012. This work was supported in part by the China National Natural Science Foundation under Grants 61004035, 61175113, 61100056, and 51105076 and in part by the National Basic Research Program of China under Grants 2010CB328100 and 2011CB302804. This paper was recommended by Associate Editor M. P. Fanti.
Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
KW - Algebraic systems
KW - Petri nets (PNs)
KW - discrete event systems (DESs)
KW - net transformation
KW - reduction
KW - refinement
UR - http://www.scopus.com/inward/record.url?scp=84865442236&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865442236&partnerID=8YFLogxK
U2 - 10.1109/TSMCA.2012.2186440
DO - 10.1109/TSMCA.2012.2186440
M3 - Article
AN - SCOPUS:84865442236
VL - 42
SP - 1244
EP - 1255
JO - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
JF - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
SN - 1083-4427
IS - 5
M1 - 6168848
ER -