Polynomial algorithms for the synthesis of hazard-free circuits from signal transition graphs

Methods for the synthesis of asynchronous circuits from signal transition graphs (STGs) have commonly used the state graph to solve the two main steps of this process: the state assignment problem and the generation of hazard-free logic. The size of the state graph can be of order O(2/sup n/), where n is the number of signals of the circuit. As synthesis tools for asynchronous systems start to mature, the size of the STGs increases and the exponential algorithms that work on the state graph become obsolete. This paper presents alternative algorithms that work in polynomial time and, therefore, avoid the generation of the SG. With the proposed algorithms, STGs can be synthesized and hazard-free circuits generated in extremely low CPU times. Improvements in two or three orders of magnitude (from hours to seconds) with respect to existing algorithms are achieved when synthesizing fairly large STGs.