Interactive Petri nets

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

Research output: Contribution to journalArticlepeer-review

50 Scopus citations


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
Issue number2
StatePublished - 2013

All Science Journal Classification (ASJC) codes

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


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


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

Cite this