IEEE Transactions on Systems Man and Cybernetics Systems · 2015 · 10 citations · 19 references
Circuit ComplexityPetri NetComputational Complexity TheoryEngineeringReachability ProblemSoftware EngineeringComputational ComplexityCommunication ComplexityWorkflow ModellingSoftware AnalysisFormal VerificationWeak SoundnessAcyclic WorkflowSystems EngineeringDiscrete MathematicsCombinatorial OptimizationDeciding SoundnessWorkflow TechnologyComputer EngineeringSoundness ProblemComputer ScienceWorkflow Management SystemComplexity TheoryProgram AnalysisAutomated ReasoningFormal MethodsWorkflow Pattern
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
Ina Ina, Rachel, Aarón · 2013 · 497 citations
Engineering, Automated Reasoning, Computational Model Theory +5