Properties and Decision Procedure for Bridge-Less Workflow Nets

Shingo YAMAGUCHI  Mohd Anuaruddin BIN AHMADON  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.2   pp.509-512
Publication Date: 2016/02/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.509
Type of Manuscript: Special Section LETTER (Special Section on Mathematical Systems Science and its Applications)
Petri net,  workflow net,  bridge-less,  necessary and sufficient condition,  polynomial-time procedure,  

Full Text: PDF(384.6KB)>>
Buy this Article

Many actual systems, e.g. computer programs, can be modeled as a subclass of Petri nets, called bridge-less workflow nets. For bridge-less workflow nets, we revealed the following properties: (i) any acyclic bridge-less workflow net is free choice; (ii) an acyclic bridge-less workflow net is sound iff it is well-structured; and (iii) any sound bridge-less workflow net is well-structured. We also proposed a necessary and sufficient condition to decide whether a given workflow net is bridge-less, and then constructed a polynomial-time procedure for it.