Title :
Output-Determinacy and Asynchronous Circuit Synthesis
Author :
Khomenko, Victor ; Schaefer, Mark ; Vogler, Walter
Author_Institution :
Newcastle Univ., Newcastle
Abstract :
Signal Transition Graphs (STG) are a formalism for the description of asynchronous circuit behaviour. In this paper we propose (and justify) a formal semantics of nondeterministic STGs with dummies and OR-causality. For this, we introduce the concept of output-determinacy, which is a relaxation of determinism, and argue that it is reasonable and useful in the speed-independent context. With our theory we improve an STG decomposition algorithm, which can alleviate state explosion.
Keywords :
asynchronous circuits; graph theory; network synthesis; asynchronous circuit synthesis; output-determinacy synthesis; signal transition graphs; speed-independent context; state explosion; Asynchronous circuits; Circuit synthesis; Clocks; Computer science; Delay; Explosions; Labeling; Signal design; Signal synthesis; State-space methods; OR-causality.; STG; asynchronous; circuits; decomposition; output-determinacy;
Conference_Titel :
Application of Concurrency to System Design, 2007. ACSD 2007. Seventh International Conference on
Conference_Location :
Bratislava
Print_ISBN :
0-7695-2902-X
DOI :
10.1109/ACSD.2007.57
