Polynomial Time Solvability of Response Property for Sound Acyclic Free Choice Workflow Nets
Atsushi Ohta, Ryosuke Fujii, Kohkichi Tsuji · 2019 34th International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC) · 2019
Petri net is a mathematical tool for concurrent discrete event systems. This paper studies computational complexity to decide whether the transition A responds to B, given a pair of transitions A and B. This problem is shown to be verified in deterministic polynomial time for sound acyclic free choice workflow nets.