Structural Methods for the Synthesis of Speed-Independent Circuits

The synthesis of asynchronous circuits is inherently complex for two different aspects. Firstly, the required cumbersome theoretical analysis introduces restrictive correctness conditions that complicate the synthesis process. Secondly, even for small asynchronous systems, its inherent concurrency implies the analysis of a huge number of states. This vast space of states requires computation intensive methods that often cannot be successfully completed. This work tackles the synthesis of asynchronous circuits from a new perspective, overcoming both the analysis and computation complexity bottlenecks. The tackled problem starts from behavioral descriptions of asynchronous circuits based on a Petri net modeling formalism. The asynchronous circuits to be generated are described by means of a class of interpreted Petri nets named Signal Transition Graphs (STGs). Based on a subset of this mathematical formalization (the free-choice STGs), the steps that should be followed in the synthesis p..