| |
Rajit Manohar and Yoram Moses
In a seminal 1990 paper [9], Martin presents the
C-element Theorem which implies, roughly, that the class of
purely delay insensitive (DI) circuits is fundamentally limited
in the set of functions it can implement. We provide circuit
examples, both DI and not DI, that violate assumptions or results
from [9], showing that the set of circuits considered by [9] is more
limited than one might expect---and hence, the results from [9]
are weaker than previously thought. In this paper we address
this issue and amend matters. We use a model of circuits that
naturally captures DI properties, and in particular admits all of
our circuit examples. We prove the Eventual C-element Theorem
for DI circuits. This is a variant of the C-element Theorem that
similarly implies that the class of DI circuits is very limited.
The proof of the new theorem uses novel techniques, and in
particular makes use of a combinatorial property not present in
previous work. With the new result, Martin's original insight and
its profound implications are restored and provided with a new
mathematical justification.
|
|
