Complexity of the soundness problem of bounded workflow nets

• Main Authors: LIU, Guan Jun, SUN, Jun, LIU, Yang, DONG, Jin Song
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2012
• Subjects: Petri nets; workflow nets; workflow nets with reset arcs; soundness; co-NP-hardness; PSPACE-hardness; Programming Languages and Compilers; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/5013; https://ink.library.smu.edu.sg/context/sis_research/article/6016/viewcontent/Complexity_of_the_Soundness_Problem_of_Bounded_Workflow_Nets.pdf
• Institution: Singapore Management University

Classical workflow nets (WF-nets) are an important class of Petri nets that are widely used to model and analyze workflow systems. Soundness is a crucial property that guarantees these systems are deadlock-free and bounded. Aalst et al. proved that the soundness problem is decidable, and proposed (b...