Polynomial Time Verification of Protocol Inheritance between Acyclic Extended Free-Choice Workflow Nets and Their Subnets


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E96-A   No.2   pp.505-513
Publication Date: 2013/02/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E96.A.505
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)
Category: Concurrent Systems
workflow net,  behavioral inheritance,  protocol inheritance,  necessary and sufficient condition,  polynomial time procedure,  

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

A workflow net N may be extended as another workflow net N' by adding nodes and arcs. N' is intuitively called a subclass of N under protocol inheritance if we cannot distinguish those behaviors when removing the added transitions. Protocol inheritance problem is to decide whether N' is a subclass of N under protocol inheritance. It is known that the problem is decidable but is intractable. Even if N is a subnet of N', N' is not always a subclass of N under protocol inheritance. In this paper, limiting our analysis to protocol inheritance between acyclic extended free-choice workflow nets and their subnets, we gave a necessary and sufficient condition on the problem. Based on the condition, we also constructed a polynomial time procedure for solving the problem.