Understanding Basic Automata Theory in the Continuous Time Setting

• Autorzy: Trakhtenbrot B.A.
• Języki publikacji: EN

Abstrakty

EN

Paradigms, in which continuous time is involved in cooperation with, or instead of, discrete time appear now in different areas related to automata, logic and interaction. Unfortunately, they are accompanied by a plethora of definitions, terminology and notation, which is not free of ad-hoc and ambiguous decisions. The overuse of definitions from scratch of intricate notions without a previous, explicit core of basic generic notions engenders further models and formalisms, and it is not clear where to stop. Hence (quoting J.Hartmanis), the challenge ``to isolate the right concepts, to formulate the right models, and to discard many others, that do not capture the reality we want to understand...". We undertake this challenge wrt some automata-theoretic concepts and issues that appear in the literature on continuous-time circuits and hybrid automata, by keeping to the following guidelines: 1. Building on Basic Automata Theory. 2. Coherence with original or potential discrete-time paradigms, whose continuous-time analogs and/or mutants we would like to understand. 3. Functions, notably input/output behavior of devices, should not be ignored in favor of sets (languages) accepted by them. The paper outlines the approach which emerged in previous research [PRT, RT, T3, T4, R] and in teaching experience [T0, T2]. As an illustration we offer a precise explanation of the evasive relationship between hybrid automata, constrained automata and control circuits.

Słowa kluczowe

EN

automata theory; paths and sets of paths; jump and flows; input-output; Constrained Automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 62, nr 1
• Strony: 69--121
• Opis fizyczny: Bibliogr. 38 poz., rys.

Twórcy

autor

Trakhtenbrot B.A.

• School of Computer Science, Tel Aviv University, Tel Aviv, Israel 69978,

Bibliografia

• [AD] Alur R., Dill D.: A theory of timed automata. Theoretical Computer Science 126. pp.183-235, 1994.
• [AFH] Alur R., Fix L., Henzinger T.: A deterministic class of timed automata. Proc. CAV94, LNCS 818, pp. 1-13.
• [AH] Alur R., Henzinger T.: Logics and models for real time: theory in practice. LNCS 600 (1992) pp. 74-106.
• [ACH*] Alur A., Courcoubetis C. Halbwachs N., Henzinger T., Pei-Sin Ho, Nicollin X., Olivero A., Sifakis J., Yovine S. The Algorithmic Analysis of Hybrid Systems, Theoretical Computer Science 138. pp.3-34, 1995.
• [Ar] Artstein Z.: Examples of stabilization with hybrid feedback. LNCS 1066 (1996) pp. 173-185.
• |ACM] Asarin E., Caspi P., Maler O., A Kleene theorem for timed automata. Proc. I2th IEEE Symposium on Logic in Computer Science, pp. 160-171. 1997 LNCS 999, Springer, 1995
• [As] Asarin E. Equations on timed languages. Hybrid Systems: Computation and Control, pp. 1-12. LNCS vol. 1386, 1998.
• [ABD*] Asarin E., Bournez O., Dang Th., Maler O., Pnueli A.: Effective synthesis of switching controllers for linear systems. Proceedings of the IEEE, vol. 88, No 7, July 2000.
• [AMPS] Asarin E., Maler O., Pnuell A., Sifakis J.: Controller synthesis for timed automata. Proc. IFAC Symp, on System Structure and Control, pp. 469-474. Elsevier, 1998.
• [B] Berry G.: The constructive semantics of pure esterel, Technical Report (Draft Version 1.2). April 1996.
• [Br] Broy M.: Semantics of finite and infinite networks of concurrent communicating agents. Distributed Computing 2 (1987) 13-31.
• [BW] Burks A.W., Wright J.B.: Theory of logical nets. Proceedings of the I.R.E., 1953.
• [DN] Davoren J.M., Nerode A.: Logics for hybrid systems. Proceedings of the IEEE, vol. 88. No 7, July 2000.
• [H] Henzinger T.: The theory of hybrid automata. Proceedings of the IEEE (1996) 278-292.
• [HW] Henzinger T., Wong-Toi H., Linear Phase-Portrait Approximations for Nonlinear Hybrid Systems, Hybrid Systems III, LNCS, vol. 1066. pp. 377-388, 1996.
• [HR] Hirshfeld Y., Rabinovich A.: Logic for real time: decidability and complexity. Fundamenta lnformaticae, This Issue.
• [KT] Kobrinsky N., Trakhtenbrot, B.A.: Introduction to the Theory of Finite Automata (Russian edition. 1962), Transl, North Holland, 1965.
• [M] Maler O.: A unified approach for studying discrete and continuous dynamical systems, Proc. 37th IEEE Conf. Dec. Contr, Tampa. USA. Dec. 1998, pp.37-42.
• [MPl] Maier O., Pnueli A.: Timing analysis of asynchronous circuits using timed automata. Proceedings CHARME’95, LNCS 987. pp. 189-205.
• [MPS] Maler O., Pnueli A., Sifakis J.: On the synthesis of discrete controllers for timed systems. Proceedings of STACS'95, LNCS 900, pp. 229-242.
• [MP3] Manna Z., Pnueli A.: Models for reactivity. Acta Informatica 30 (1993) 609-678.
• [McN] McNaughton R.: Badly timed elements and well timed nets. Technical Report 65-02, Moore-School, 1964.
• [MS] Müller O., Scholz P.: Functional specification of real-time and hybrid systems. LNCS 1201, pp.273-285, 1997.
• [OD] Olderog E.R., Dierks H.: Decomposing real-time specifications. Intern. Symp. COMPOS"97. LNCS 1536. pp. 465-489.
• [P] Pardo D. Timed Automata: Transducers and Circuits, Technical Report, Tel Aviv University, 50 p. 1997.
• [PRT] Pardo D., Rabinovich A., Trakhtenbrot. B.A.: Synchronous circuits over continuous time: Feedback Reliability and Completeness. Fundamenta Informaticae. this issue.
• [R02] Rabinovich A. Finite variability interpretation of monadic logic of order. Theoretical Computer Science. 275(1-2): 111-125(2002).
• [R] Rabinovich A. Finite automata over continuous time, Theoretical Computer Science 300 (2003)331-363.
• [RT] Rabinovich A., Trakhtenbrot B.: From finite automata toward hybrid systems. Proceedings FCT’97, LNCS.
• [RW] Ramadge P.J., Wonham W.M.: The control of discrete event systems, Proc. of the IEEE'77. pp. 81-98 1989.
• [SI] Sontag E.: Mathematical Control Theory: Deterministic Finite Dimensional Systems, Springer, N.Y., 1990.
• [T0] Trakhtenbrot B.A.: Lecture Notes of a Course on Verification of Software and Hardware. Tel-Aviv University. Fall 1994.
• [T1] Trakhtenbrot B.A.: Origins and metamorphose of the trinity: logics, nets, automata, Proceedings, Lies’95.
• [T2] Trakhtenbrot B.A.: Automata and hybrid systems. Lecture Notes on a course at Uppsala University, Fall 1997.
• [T3] Trakhtenbrot B.A.: Automata and their interaction: definitional suggestions. FCT99, LNCS 1684, pp.54-89. 1999.
• [T4] Trakhtenbrot B.A.: Automata, circuits and hybrids: facets of continuous time. Proceedings ICALP’2001 1
• [VdSS] Van der Schaft, Schumacher H. An Introduction to Hybrid Dynamical Systems, Springer Verlag London, (vii=174). 2000.
• [ZM] Zhang Y. Mackworth A. Constraint nets: a semantic model for hybrid dynamic systems. Theoretical Computer Science 138, pp.211-239. 1995.