On the Complexity of Deciding Soundness of Acyclic Workflow Nets
Ferucio Laurenţiu Ţiplea, Corina Bocăneala, Raluca Chirosca · IEEE Transactions on Systems Man and Cybernetics Systems · 2015
This paper focuses on the complexity of the (weak) soundness problem of acyclic workflow (WF) nets, and two main results are established: (1) soundness of 1-bounded acyclic WF nets is co-NP-complete and (2) weak soundness of 3-bounded acyclic asymmetric-choice WF nets is co-NP-complete.