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

Author: Peter Kemper

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 LBFC-nets
can be recognised in $O(|P|^2|T|)$, which is an improvement 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 O($n^3$).

Published in:
	Application and Theory of Petri Nets 1993
	14th int. Conf. Chicago, USA
	Springer Lecture Notes in Computer Science 691