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 language | English (US) |
---|---|
Pages (from-to) | 291-302 |
Number of pages | 12 |
Journal | IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans |
Volume | 43 |
Issue number | 2 |
DOIs | |
State | Published - 2013 |
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Software
- Information Systems
- Human-Computer Interaction
- Computer Science Applications
- Electrical and Electronic Engineering
Keywords
- Co-NP-hardness
- Compatibility
- Interactive Petri nets (IPNs)
- Liveness
- Web service