Reference: A. Kovalyov and J. Esparza. A polynomial algorithm to compute the concurrency relation of free-choice signal transition graphs. In Prof. of the International Workshop on Discrete Event Systems, WODES'96, pages 1–6, Edinburgh, 1996. The Institution of Electrical Engineers. Abstract: The concurrency relation of a Petri net contains the pairs of transitions that can be concurrently enabled. We present a polynomial algorithm to compute the concurrency relation of free-choice Signal Transition Graphs, a class of Petri nets with applications to the verification and synthesis of speed-independent circuits. Suggested BibTeX entry: @inproceedings{KE96,     address = {Edinburgh},     author = {A. Kovalyov and J. Esparza},     booktitle = {Prof. of the International Workshop on Discrete Event Systems, WODES'96},     organization = {The Institution of Electrical Engineers},     pages = {1--6},     title = {A Polynomial Algorithm to Compute the Concurrency Relation of Free-Choice Signal Transition Graphs},     year = {1996} }

GZipped PostScript (55 kB) PDF (205 kB)