Time based deadlock prevention for Petri nets

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). (C) 2021 Elsevier Ltd. All rights reserved.

Automated summary

This paper investigates the deadlock prevention problem for Petri nets, showing that the time based deadlock prevention problem is decidable for bounded Petri nets and formalized as a parametric model checking problem. A symbolic approach is proposed to handle Petri nets with controllable/uncontrollable transitions.