Title :
On the Complexity of Deciding Soundness of Acyclic Workflow Nets
Author :
Tiplea, Ferucio Laurentiu ; Bocaneala, Corina ; Chirosca, Raluca
Author_Institution :
Dept. of Comput. Sci., “Alexandru Ioan Cuza” Univ. of Iasi, Iaşi, Romania
Abstract :
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.
Keywords :
Petri nets; computational complexity; decidability; 1-bounded acyclic WF nets; 3-bounded acyclic asymmetric-choice WF nets; Petri net; acyclic workflow nets; co-NP-complete problem; complexity analysis; decidability; weak-soundness problem; Complexity theory; Computer science; Cybernetics; Indexes; Petri nets; Polynomials; Semantics; Complexity; Petri net; WF system; decidability; normalsize Complexity; soundness; workflow (WF) net;
Journal_Title :
Systems, Man, and Cybernetics: Systems, IEEE Transactions on
DOI :
10.1109/TSMC.2015.2394735
