For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Polynomial Time Verification of Protocol Inheritance between Acyclic Extended Free-Choice Workflow Nets and Their Subnets
Shingo YAMAGUCHI Tomohiro HIRAKAWA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2013/02/01
Online ISSN: 1745-1337
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)>>
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.