Computational Complexity and Polynomial Time Procedure of Response Property Problem in Workflow Nets

Muhammad Syafiq BIN AB MALEK  Mohd Anuaruddin BIN AHMADON  Shingo YAMAGUCHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.6   pp.1503-1510
Publication Date: 2018/06/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017FOP0008
Type of Manuscript: Special Section PAPER (Special Section on Formal Approaches)
Category: Formal Approaches
Keyword: 
the response property,  Petri net,  process tree,  computational complexity,  polynomial time algorithm,  

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


Summary: 
Response property is a kind of liveness property. Response property problem is defined as follows: Given two activities α and β, whenever α is executed, is β always executed after that? In this paper, we tackled the problem in terms of Workflow Petri nets (WF-nets for short). Our results are (i) the response property problem for acyclic WF-nets is decidable, (ii) the problem is intractable for acyclic asymmetric choice (AC) WF-nets, and (iii) the problem for acyclic bridge-less well-structured WF-nets is solvable in polynomial time. We illustrated the usefulness of the procedure with an application example.