Synchronous Circuits over Continuous Time: Feedback Reliability and mpleteness

Issue title: Continuous Time Paradigms in Logic and Automata

Article type: Research Article

Authors: Pardo, D. | Rabinovich, A. | Trakhtenbrot, B.A.

Affiliations: School of Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel 69978

Abstract: To what mathematical models do digital computer circuits belong? In particular: (i) (Feedback reliability.) Which cyclic circuits should be accepted? In other words, under which conditions is causally faithful the propagation of signals along closed cycles of the circuit? (ii) (Comparative power and completeness.) What are the appropriate primitives upon which circuits may be (or should be) assembled? There are well-known answers to these questions for circuits operating in discrete time, and they point on the exclusive role of the unit-delay primitive. For example: (i) If every cycle in the circuit N passes through a delay, then N is feedback reliable. (ii) Every finite-memory operator F is implementable in a circuit over unit-delay and pointwise boolean gates. In what form, if any, can such phenomena and results be extended to circuits operating in continuous time? This is the main problem considered (and, hopefully, solved to some extent) in this paper. In order to tackle the problems one needs more insight into specific properties of continuous time signals and operators that are not visible at discrete time.

Journal: Fundamenta Informaticae, vol. 62, no. 1, pp. 123-137, 2004