Synchronous Circuits over Continuous Time: Feedback Reliability and Completeness

• Autorzy: Pardo D. , Rabinovich A. , Trakhtenbrot B.A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

mathematical model; circuits; synchronous circuits

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 62, nr 1
• Strony: 123--137
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Pardo D.

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

autor

Rabinovich A.

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

autor

Trakhtenbrot B.A.

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

Bibliografia

• [1] R. AlurandD. Dill. A theory of timed automata. Theoretical Computer Science,126:183-235,1994.
• [2] R. Alur. Timed Automata. CAV99, LNCS Vol. 1633:8-22,1999.
• [3] Berry G., The Constructive Semantics of Pure Esterel, Technical Report (Draft Version 1.2), April 1996.
• [4] Burks, A.W., Wright, J.B.: Theory of logical nets. Proceedings of the LR.E., 1953.
• [5] N. Kobrinski and B. A. Trakhtenbrot. Introduction to the theory of Finite Automata, North Holland 1965.
• [6] Kratko M.I. Undecidability of completeness for finite automata, Doklady AN SSSR, vol 155, No 1, 1964, pp 35-37.
• [7] Letichevski A.A. Completeness conditions for finite automata. Journal for computational mathematics and mathematical physics, Vol 1, No 4 (1961) pp. 702-710.
• [8] R. McCulloch and W. Pitts. A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophysics, 5, 1943, pp. 115-133.
• [9] McNaughton. Badly Timed Elements and Well Timed Nets. Technical Report 65-02, Moore School, 1964.
• [10] O. Maler and A. Pnueli. Timing analysis of Asynchronous Circuits using CHARME 1995: Lecture Notes in Computer Science, Vol. 987:189-205, Springer, 1995.
• [11] O. Muller and P. Scholz. Functional Specification of Real-Time and Hybrid Systems. HART97 LNCS vol 1201:273-285,1997.
• [12] D. Pardo. Timed Automata: Transducers and Circuits. M.Sc. thesis, Tel Aviv University, 1997.
• [13] D. Pardo, A. Rabinovich and B. A. Trakhtenbrot. Circuits over Continuous Time Technical Report, Tel Aviv University, 1997.
• [14] A. Rabinovich. Finite Automata over continuous time. Theoretical Computer Science 300 (2003) pp. 331-363.
• [15] A. Rabinovich and B. A. Trakhtenbrot. From Finite Automata toward Hybrid Systems. Proc. FCT97, LNCS 1450:411-422, Springer, 1997.
• [16] B. Trakhtenbrot. Origins and Metamorphoses of the Trinity: Logics, Nets, Automata. In Proceedings of Lies, 1995.
• [17] B. A. Trakhtenbrot: Automata, Circuits, and Hybrids: Facets of Continuous Time. ICALP 2001, LNCS 2076:4-23.
• [18] B. Trakhtenbrot. Understanding Automata Theory in the continuous time setting. This volume.
• [19] T. Wilke. Specifying Timed State Sequences in Powerful Decidable Logics and Timed Automata, FTFRFT, 1994.