工作流网络健全性问题的复杂性

经典工作流网(简称WF-net)是Petri网的重要子类,被广泛用于建模和分析工作流系统。 健全性是工作流系统的关键属性,并确保这些系统无死锁且不受限制。 Aalst等。 事实证明,稳健性问题对于WF网络是可以决定的,并且对于自由选择WF网络可以是多项式可解的。 本文证明了WF网络的稳健性问题是PSPACE难解决的。 此外,证明了有界WF网络的健全性问题是PSPACE完全的。 根据以上结论,可以得出结论,对于带有复位或抑制弧的有界WF网络(简称ReWF网络和InWF网络),健全性问题也是PSPACE完全的。 ReWF和InWF网络是WF网络的两个扩展,其稳健性问题已由Aalst等人证明。 不可思议。 此外,我们证明,对于非对称选择WF网络来说,健全性问题对共NP困难,因为WF-net是更大的类别,并且与自由选择WF网络相比,可以建模更多的交互和资源分配情况。