Extensions of asynchronous circuits and the delay problem I. Good extensions and the delay problem of the first kind

摘要

Delays of signal propagation inherent in the wires interconnecting the logical elements of an asynchronous circuit sometimes cause erroneous behavior of the circuit. This problem is known as the delay problem, of which this paper attempts to make a full analysis from the broadest possible perspective. Basic to our theory is the concept of extensions. An extension C* of a circuit C is another circuit having hidden nodes in addition to the nodes of C. A requirement is introduced for C* to be “practically identical” to C, and conditions are derived for it to hold. A model of the delays within the wires is established, and the significance of the requirement relative to this model is investigated. For a fairly broad class of configurations of the wires, a finite procedure for checking whether the delays are harmful or not is given. Part of the mathematical framework of this paper is also applicable to a number of related problems other than the delay problem.