Solving the state assignment problem for signal transition graphs

The authors propose a novel framework to solve the state assignment problem arising from the signal transition graph (STG) representation of an asynchronous circuit. They first solve the STG state assignment problem by minimizing the number of states in the corresponding finite-state machine (FSM) and by using a critical race-free state assignment technique. State signal transitions may be added to the original STG. A lower bound on the number of signals necessary to implement the STG is given. The technique significantly increases the applicability of STGs for specifying asynchronous circuits