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.
Computational Complexity and Polynomial Time Procedure of Response Property Problem in Workflow Nets
Muhammad Syafiq BIN AB MALEK Mohd Anuaruddin BIN AHMADON Shingo YAMAGUCHI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2018/06/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Formal Approaches)
Category: Formal Approaches
the response property, Petri net, process tree, computational complexity, polynomial time algorithm,
Full Text: PDF(609.5KB)
>>Buy this Article
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.