Title | ||
---|---|---|
Analysis Of Option To Complete, Proper Completion And No Dead Tasks For Acyclic Free Choice Workflow Nets |
Abstract | ||
---|---|---|
Workflow nets (WF-nets for short) are a subclass of Petri nets and are used for modeling and analysis of workflows. Soundness is a criterion of logical correctness defined for WF-nets. A WF-net is said to be sound if it satisfies three conditions: (i) option to complete, (ii) proper completion, and (iii) no dead tasks. In this paper, focusing our analysis on acyclic free choice WF-nets, we revealed that (1) Conditions (i) and (ii) of soundness are respectively equivalent to the liveness and the boundedness of its short-circuited net; (2) The decision problem for each condition of soundness is co-NP-complete; and (3) If the short-circuited net has no disjoint paths from a transition to a place (or no disjoint paths from a place to a transition), each condition can be checked in polynomial time. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1587/transfun.E102.A.336 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
Petri net, workflow net, soundness, liveness, boundedness | Theoretical computer science,Workflow nets,Mathematics | Journal |
Volume | Issue | ISSN |
E102A | 2 | 0916-8508 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
1 |