TY - JOUR
T1 - Soundness of workflow nets : classification, decidability, and analysis
AU - Aalst, van der, W.M.P.
AU - Hee, van, K.M.
AU - Hofstede, ter, A.H.M.
AU - Sidorova, N.
AU - Verbeek, H.M.W.
AU - Voorhoeve, M.
AU - Wynn, M.T.
PY - 2011
Y1 - 2011
N2 - Workflow nets, a particular class of Petri nets, have become one of the standard ways to model and analyze workflows. Typically, they are used as an abstraction of the workflow that is used to check the so-called soundness property. This property guarantees the absence of livelocks, deadlocks, and other anomalies that can be detected without domain knowledge. Several authors have proposed alternative notions of soundness and have suggested to use more expressive languages, e.g., models with cancellations or priorities. This paper provides an overview of the different notions of soundness and investigates these in the presence of different extensions of workflow nets. We will show that the eight soundness notions described in the literature are decidable for workflow nets. However, most extensions will make all of these notions undecidable. These new results show the theoretical limits of workflow verification. Moreover, we discuss some of the analysis approaches described in the literature.
AB - Workflow nets, a particular class of Petri nets, have become one of the standard ways to model and analyze workflows. Typically, they are used as an abstraction of the workflow that is used to check the so-called soundness property. This property guarantees the absence of livelocks, deadlocks, and other anomalies that can be detected without domain knowledge. Several authors have proposed alternative notions of soundness and have suggested to use more expressive languages, e.g., models with cancellations or priorities. This paper provides an overview of the different notions of soundness and investigates these in the presence of different extensions of workflow nets. We will show that the eight soundness notions described in the literature are decidable for workflow nets. However, most extensions will make all of these notions undecidable. These new results show the theoretical limits of workflow verification. Moreover, we discuss some of the analysis approaches described in the literature.
U2 - 10.1007/s00165-010-0161-4
DO - 10.1007/s00165-010-0161-4
M3 - Article
SN - 0934-5043
VL - 23
SP - 333
EP - 363
JO - Formal Aspects of Computing
JF - Formal Aspects of Computing
IS - 3
ER -