Time based deadlock prevention for Petri nets. (March 2022) - Boucheneb, Hanifa; Barkaoui, Kamel; Xing, Qian; Wang, KuangZe; Liu, GaiYun; Li, ZhiWu
Abstract: This paper investigates the deadlock prevention problem for Petri nets (PN), in which the control is performed by appropriately setting time constraints on transitions, in terms of firing intervals. We show that this time based deadlock prevention (TBDP) problem is decidable for bounded PN and can be formalised as a parametric model checking problem. However, in this context, the parametric model checking faces a severe state explosion problem. To deal with this limitation, we propose a symbolic approach that abstracts firing order constraints and bypasses the use of parameter domains with their associated very costly operations. Both approaches can handle, as an input model, a (time) PN with controllable/uncontrollable transitions. In such a case, they expose whether or not the firing intervals of the controllable transitions of the input model can be restricted so as to force the deadlock freeness (i.e., there is no marking with no enabled transitions).