IEEE Transactions on Systems Man and Cybernetics Systems · 2015 · 11 citations · 19 references
ComputingComputer ScienceAlgorithmsFormal MethodsTheory Of ComputationAlgorithmic ComplexityComplexity TheoryComputational ComplexityPetri NetsStructural ComplexityWorkflow OrchestrationCompleteness ResultsComplexitySoundnessSoundness ProofsSoundness TheoremsWorkflow Nets
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.
19
Introduction to the Theory of Computation
Michael Sipser · ACM SIGACT News · 1996 · 2.8K citations
Introduction to the Theory of Computation
Complexity results for 1-safe nets
Allan Cheng, Javier Esparza, Jens Palsberg · Theoretical Computer Science · 1995 · 134 citations