Title: 	O(|P||T|)-Algorithm to Compute a Cover of S-components in EFC-nets

Author: Peter Kemper

Abstract: 

  For a strongly connected Extended-Free-Choice Net (EFC-net) N the
  algorithm given in this paper either finds a cover of S-components
  or recognizes that N is not well-formed. Well-formedness denotes the
  existence of a live and bounded marking for N. The algorithm is also
  adaptable to compute a cover of T-components. The time complexity is
  O(|P||T|).  According to the Rank Theorem, finding a cover of S-
  and T-components is useful for recognizing well-formed EFC-nets.
  Employing the new algorithm allows to decide well-formedness for
  EFC-nets in O(|P||T|^2). 


Published in:
	Forschungbericht Nr. 543/1994 
	Fachbereich Informatik, Universitaet Dortmund