论文部分内容阅读
Inter-organizational workflow nets(IWF-nets) can well model the interactions among multiple processes by sending/receiving messages. Compatibility and weak compatibility are crucial properties for IWF-nets.The latter guarantees that a system is deadlock-free and livelock-free while the former also guarantees that it has no dead tasks. Our previous work proved that the(weak) compatibility problem is PSPACE-complete for safe IWF-nets. This paper defines a class of IWF-nets in which some simple circuits are allowed. Necessary and sufficient conditions are presented to decide compatibility and weak compatibility for this class, and they are dependent on the net structures only. Algorithms are developed based on these conditions. In addition, we show that the traditional net structures like siphon cannot be easily used to decide the(weak) compatibility of IWF-nets.
Inter-organizational workflow nets (IWF-nets) can well model the interactions among multiple processes by sending / receiving messages. Compatibility and weak compatibility are crucial properties for IWF-nets. The latter guarantees that a system is deadlock-free and livelock-free while the former also guarantees that it has no dead tasks. Our previous work demonstrated that the (weak) compatibility problem is PSPACE-complete for safe IWF-nets. This paper defines a class of IWF-nets in which some simple circuits are allowed. Necessary and sufficient conditions are presented to decide compatibility and weak compatibility for this class, and they are dependent on the net structures only. In addition, we show that the traditional net structures like siphon can not be easy used to decide the (weak) compatibility of IWF-nets.