| |
Rajit Manohar and Yoram Moses
A model of processes that interact via asynchronous
wires carrying Boolean signals is presented. In this model,
modules, called processes, can be made arbitrarily complex, can
maintain local memory and can have an arbitrary number of
inputs and outputs. A variety of circuit models can be represented
by networks of signalling processes. It is shown that in a network
of signalling processes consisting solely of single-ouput processes
and forks, every module is an eventual C element. Consequently,
the computational power of such a network is severely limited.
This establishes that the celebrated C-element property of DI
circuits follows solely from the fact that single output modules
communicate over stable asynchronous wires. Conversely, it is
shown that any Boolean function can be implemented using
four-input/two-output processes where every process is either one gate
(single output) or a pair of gates (two output).
|
|
