Interactive Petri nets

Guan Jun Liu, Chang Jun Jiang, Meng Chu Zhou, Peng Cheng Xiong

Research output: Contribution to journalArticlepeer-review

41 Scopus citations

Abstract

Such concurrent systems as Web services and workflow systems can be viewed as a composition of a set of subsystems. Subsystems interact with each other through a set of message channels in order to perform a task. This work defines a class of Petri nets called interactive Petri nets (IPNs) to model these systems. IPNs can be used to analyze their behavior, find potential problems, and then improve their designs. Compatibility is an important concept for a composed system and reflects the possibility of correct/proper interaction among its subsystems. In order to characterize different cooperative abilities in practice, compatibility and weak compatibility are defined for IPNs. Some relationships among (weak) compatibility, liveness, reversibility, and boundedness are revealed. Based on them, this work proves that the (weak) compatibility problem is co-NP-hard. A taxonomy is also presented for IPNs in order to explore whether some subclasses can be analyzed efficiently. Based on it, we can identify several IPN subclasses, some of which can be analyzed in polynomial time.

Original languageEnglish (US)
Pages (from-to)291-302
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
Volume43
Issue number2
DOIs
StatePublished - Jan 1 2013

All Science Journal Classification (ASJC) codes

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

Keywords

  • Co-NP-hardness
  • Compatibility
  • Interactive Petri nets (IPNs)
  • Liveness
  • Web service

Fingerprint Dive into the research topics of 'Interactive Petri nets'. Together they form a unique fingerprint.

Cite this