In: Discrete Mathematics, Vol. 29, pages 195-210. 1990.
Abstract: The authors show that by reformulating the conditions defining deadlocks (traps, preconservative components (pcc's)) in terms of logic programming problems featuring the special structure known as Horn-satifiability, polynomial algorithms can be derived for solving the following problems: finding of minimal deaklocks (traps, pcc's) containing a specified subset of places; finding a covering of the places by deadlocks (traps, pcc's). The approach presented in this paper appears to provide an appropriate framework for addressing algorithmic and computational problems related to Petri nets.
Keywords: deadlocks; traps; horn-satisfiability solution; polynomially solvable problem; deadlock; trap; preconservative component.