Reduction and refinement by algebraic operations for Petri net transformation

Jun Li, Meng Chu Zhou, Xianzhong Dai

Research output: Contribution to journalArticlepeer-review

40 Scopus citations

Abstract

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.

Original languageEnglish (US)
Article number6168848
Pages (from-to)1244-1255
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
Volume42
Issue number5
DOIs
StatePublished - 2012

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications

Keywords

  • Algebraic systems
  • Petri nets (PNs)
  • discrete event systems (DESs)
  • net transformation
  • reduction
  • refinement

Fingerprint

Dive into the research topics of 'Reduction and refinement by algebraic operations for Petri net transformation'. Together they form a unique fingerprint.

Cite this