In: Proc. 2nd Workshop on Hardware Design and Petri Nets (HWPN'99) of the 20th Int. Conf. on Application and Theory of Petri Nets (PN'99), 21 June 1999, Williamsburg, VA, pages 15-34. 1999.
Also in: Yakovlev, A.; Gomes, L.; Lavagno, L.: Hardware Design and Petri Nets, pages 107-126. Boston: Kluwer Academic Publishers, 2000.
Abstract: Signal transition graphs (STGs) are a class of interpreted Petri nets which are used for the verification and synthesis of speed-independent circuits. Some problems of analysis and synthesis of signal transition graphs and Petri nets are studied in this paper. Several synthesis techniques for STGs have been proposed which require knowledge of the concurrency relation of the net, i.e., the pairs of transitions that can become concurrently enabled at some reachable marking. This paper generalizes the previous method of computing concurrency relation on free-choice signal transition graphs to signal transition graphs which are not necessarily free-choice. The proof is closely related to a reduction method.
Keywords: Petri nets, concurrency relation, polynomial algorithms, reduction methods, regular signal transition graphs.