Synthesis of asynchronous circuits-testing unique circuit behavior of signal transition graphs

An important work related to the synthesis of asynchronous circuits from a signal transition graph (STG) specification is studied in this paper. The work is to test the satisfaction of one-token restriction. The one-token restriction is essential for an STG to avoid possible ambiguity in a behavioral specification. A graph reduction method which uses five reduction operations: series, parallel, unique-cycle, group-collapse, and conflict-block reductions, is proposed to achieve the task. Experimental results show that our proposed techniques are also very efficient for STGs of very large sizes