Summary
International Technical Conference on Circuits/Systems, Computers and Communications
2016
Session Number:M2-1
Session:
Number:M2-1-2
On Each Condition of Soundness for Acyclic Free Choice Workflow Nets
Shingo Yamaguchi, Naoki Nakahara ,
pp.121-124
Publication Date:2016/7/10
Online ISSN:2188-5079
Summary:
Workflow nets (WF-nets for short) are Petri nets which represent 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. Our result shows that for an acyclic free choice WF-net, (1) Conditions (i) and (ii) of soundness are respectively equivalent to liveness and boundedness of the short-circuited net; (2) Checking of Conditions (i) and (ii) are respectively 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), Conditions (i) and (ii) can be checked in polynomial time.