c ° 2000 Kluwer Academic Publishers. Manufactured in The Netherlands. Delay-Insensitivity and Semi-Modularity⁄

Abstract. The study of asynchronous circuit behaviors in the presence of component and wire delays has received a great deal of attention. In this paper, we consider asynchronous circuits whose components can be any non-deterministic sequential machines of the Moore type, and describe a formal model for these circuits and their behaviors under the inertial delay model. We model an asynchronous circuit C by a network N of modules with delays associated with its components and/or wires. We compute the behavior of N assuming arbitrary inertial delays in the modules, and take this behavior to be correct. We define N to be strongly delay-insensitive if its behavior remains correct in the presence of arbitrary stray delays, where correctness is defined through the notion of observational equivalence (or bisimulation), one of the strongest forms of behavioral equivalence. We introduce the notion of quasi semi-modularity, which generalizes Muller’s definition of semi-modularity to non-deterministic networks. We prove that a circuit, with all the wire delays taken into account, is strongly delay-insensitive if and only if its behavior is quasi semi-modular