Structural Methods for the Synthesis of Speed-Independent Circuits

Most existing tools for the synthesis of asynchronouscircuits from Signal Transition Graphs (STGs) derive the reachability graph for the calculation of logic equations. This paper presents novel methods exclusively based on the structural analysis of the underlying Petri net. This methodology can be applied to any STG that can be covered by State Machines and, in particular, to all live and safe free-choice STGs. Significant improvements with regard to existing structural methods are provided. The new techniques have been implemented in an experimental tool that has been able to synthesize specificationswith over10 27 markings, some of them being non-free choice. 1 Introduction Petri nets (PNs) are a powerful formalism to model concurrent systems. As a model, their most interesting feature is the capability of implicitly describing a vast state space by a succinct representation, which gracefully captures the notions of causality, concurrency and conflict between events. Petri nets..