Protocol Inheritance Preserving Soundizability Problem and Its Polynomial Time Procedure for Acyclic Free Choice Workflow Nets

Shingo YAMAGUCHI  Huan WU  

IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.5   pp.1181-1187
Publication Date: 2014/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E97.D.1181
Type of Manuscript: Special Section PAPER (Special Section on Formal Approach)
Category: Formal Construction
workflow net,  Petri net,  behavioral inheritance,  soundness,  soundizability,  polynomial time procedure,  

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

A workflow may be extended to adapt to market growth, legal reform, and so on. The extended workflow must be logically correct, and inherit the behavior of the existing workflow. Even if the extended workflow inherits the behavior, it may be not logically correct. Can we modify it so that it satisfies not only behavioral inheritance but also logical correctness? This is named behavioral inheritance preserving soundizability problem. There are two kinds of behavioral inheritance: protocol inheritance and projection inheritance. In this paper, we tackled protocol inheritance preserving soundizability problem using a subclass of Petri nets called workflow nets. Limiting our analysis to acyclic free choice workflow nets, we formalized the problem. And we gave a necessary and sufficient condition on the problem, which is the existence of a key structure of free choice workflow nets called TP-handle. Based on this condition, we also constructed a polynomial time procedure to solve the problem.