For the most recent entries see the Petri Nets Newsletter.

Deadlocks and Traps in Petri Nets as Horn-Satisfiability Solutions and some Related Polynomially Solvable Problems.

Minoux, M.; Barkaoui, K.

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.

Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography