For the most recent entries see the Petri Nets Newsletter.

Linear Time Algorithm to Find a Minimal Deadlock in a Strongly Connected Free-Choice Net.

Kemper, Peter

In: Ajmone Marsan, M.: Lecture Notes in Computer Science, Vol. 691; Application and Theory of Petri Nets 1993, Proceedings 14th International Conference, Chicago, Illinois, USA, pages 319-338. Springer-Verlag, 1993.

Abstract: This paper presents an improved algorithm, which finds a minimal deadlock containing a given place p in a strongly connected Free-Choice net (FC-net). Its worst case time complexity is linear in the size of the net. The interest in finding such deadlocks arises from recognising structurally live and bounded FC-nets (LBFC-nets) where finding structural deadlocks efficiently is crucial for the algorithm's time complexity. Employing this new algorithm within LBFC-nets can be recognised in 0(|P|²|T|), which is a reduction by one order of magnitude. Furthermore this marks a lower limit for the complexity of algorithms based on the rank theorem as long as the computation of a matrix rank requires 0(n³).


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

Back to the Petri Nets Bibliography