www.elsevier.com/locate/tcs Delay-insensitivity and ternary simulation(

Consider a network N constructed from a set of modules interconnected by wires. Suppose that there is a formal specication for N, and that the behavior of N satises this specication. Let N ̂ consist of the same modules, but suppose that these modules and the interconnecting wires have arbitrary delays. We say that N is delay-insensitive if the behavior of any network N̂ de ned as above still satises . An important problem in asynchronous circuits is to determine, given a specication and a set T of module types, whether there exists a delay-insensitive network of modules from T with a behavior satisfying . If such a network exists, we say that it implements delay-insensitively. In the case where the components are logic gates, it is known that very few specications have delay-insensitive implementations. The proofs of several such results involve \ternary simulation " { an analysis method based on ternary algebra { and rely on a key theorem linking binary analysis and ternary simulation. In this paper we survey the known results concerning delay-insensitivity, and outline one proof that a simple specicatio