We provide an overview of theories of continuous time computation. These theories allow us to understand both the hardness of questions related to continuous time dynamical systems and the computational power of continuous time analog models. We survey the existing models, summarizing results, and point to relevant references in the literature.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aaronson, S. (2005). NP-complete problems and physical reality. ACM SIGACT News, 36(1):30-52.
Abdi, H. (1994). A neural network primer. Journal of Biological Systems, 2:247-281.
Adleman, L. M. (1994). Molecular computation of solutions to combinatorial problems. Science, 266:1021-1024.
Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T. A., Ho, P. H., Nicollin, X., Oliv-ero, A., Sifakis, J., and Yovine, S. (1995). The algorithmic analysis of hybrid systems. Theoretical Computer Science, 138(1):3-34.
Alur, R. and Dill, D. L. (1990). Automata for modeling real-time systems. In Pater-son, M., editor, Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, July 16-20, 1990, Proceedings, volume 443 of Lecture Notes in Computer Science, pages 322-335. Springer.
Alur, R. and Dill, D. L. (1994). A theory of timed automata. Theoretical Computer Science, 126(2):183-235.
Alur, R. and Madhusudan, P. (2004). Decision problems for timed automata: A survey. In Bernardo, M. and Corradini, F., editors, Formal Methods for the Design of Real-Time Systems, International School on Formal Methods for the Design of Computer, Com-munication and Software Systems, SFM-RT 2004, Bertinoro, Italy, September 13-18, 2004, Revised Lectures, volume 3185 of Lecture Notes in Computer Science, pages 1-24. Springer.
Arnold, V. I. (1989). Mathematical methods of classical mechanics, volume 60 of Grad-uate Texts in Mathematics. Springer, second edition.
Artobolevskii, I. (1964). Mechanisms for the Generation of Plane Curves. Macmillan, New York. Translated by R.D. Wills and W. Johnson.
Asarin (2004). Challenges in timed languages: From applied theory to basic theory. Bulletin of the European Association for Theoretical Computer Science, 83:106-120.
Asarin, E. (1995). Chaos and undecidabilty (draft). Avalaible in http://www. liafa.jussieu.fr/$\tilde{\}$asarin/.
Asarin, E. (1998). Equations on timed languages. In Henzinger, T. A. and Sastry, S., editors, Hybrid Systems: Computation and Control, First International Workshop, HSCC’98, Berkeley, CA, April 13-15, 1998, Proceedings, volume 1386 of Lecture Notes in Computer Science, pages 1-12. Springer.
Asarin, E. (2006). Noise and decidability. Continuous Dynamics and Computabil-ity Colloquium. Video and sound available trough “Diffusion des savoirs de l’Ecole Normale Supérieure,” on http://www.diffusion.ens.fr/en/index.php? res=conf\&idconf=1226.
Asarin, E. and Bouajjani, A. (2001). Perturbed Turing machines and hybrid systems. In Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, pages 269-278, Los Alamitos, CA. IEEE Computer Society Press.
Asarin, E., Caspi, P., and Maler, O. (1997). A Kleene theorem for timed automata. In Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, pages 160-171, Warsaw, Poland. IEEE Computer Society Press.
Asarin, E., Caspi, P., and Maler, O. (2002). Timed regular expressions. Journal of the ACM, 49(2):172-206.
Asarin, E. and Collins, P. (2005). Noisy Turing machines. In Caires, L., Italiano, G. F., Monteiro, L., Palamidessi, C., and Yung, M., editors, Automata, Languages and Pro-gramming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 of Lecture Notes in Computer Science, pages 1031-1042. Springer.
Asarin, E. and Dima, C. (2002). Balanced timed regular expressions. Electronic Notes in Theoretical Computer Science, 68(5).
Asarin, E. and Maler, O. (1998). Achilles and the tortoise climbing up the arithmetical hierarchy. Journal of Computer and System Sciences, 57(3):389-398.
Asarin, E., Maler, O., and Pnueli, A. (1995). Reachability analysis of dynamical systems having piecewise-constant derivatives. Theoretical Computer Science, 138(1):35-65.
Asarin, E. and Schneider, G. (2002). Widening the boundary between decidable and undecidable hybrid systems. In Brim, L., Jancar, P., Kretínský, M., and Kucera, A., editors, CONCUR 2002 - Concurrency Theory, 13th International Conference, Brno, Czech Republic, August 20-23, 2002, Proceedings, volume 2421 of Lecture Notes in Computer Science, pages 193-208. Springer.
Asarin, E., Schneider, G., and Yovine, S. (2001). On the decidability of the reachability problem for planar differential inclusions. In Benedetto, M. D. D. and Sangiovanni-Vincentelli, A. L., editors, Hybrid Systems: Computation and Control, 4th International Workshop, HSCC 2001, Rome, Italy, March 28-30, 2001, Proceedings, volume 2034 of Lecture Notes in Computer Science, pages 89-104. Springer.
Beauquier, D. (1998). Pumping lemmas for timed automata. In Nivat, M., editor, Foun-dations of Software Science and Computation Structure, First International Conference, FoSSaCS’98, Held as Part of the European Joint Conferences on the Theory and Prac-tice of Software, ETAPS’98, Lisbon, Portugal, March 28 - April 4, 1998, Proceedings, volume 1378 of Lecture Notes in Computer Science, pages 81-94. Springer.
Ben-Hur, A., Feinberg, J., Fishman, S., and Siegelmann, H. T. (2003). Probabilistic anal-ysis of a differential equation for linear programming. Journal of Complexity, 19(4):474-510.
Ben-Hur, A., Feinberg, J., Fishman, S., and Siegelmann, H. T. (2004a). Random ma-trix theory for the analysis of the performance of an analog computer: a scaling theory. Physics Letters A, 323(3-4):204-209.
Ben-Hur, A., Roitershtein, A., and Siegelmann, H. T. (2004b). On probabilistic analog automata. Theoretical Computer Science, 320(2-3):449-464.
Ben-Hur, A., Siegelmann, H. T., and Fishman, S. (2002). A theory of complexity for continuous time systems. Journal of Complexity, 18(1):51-86.
Blondel, V. D. and Tsitsiklis, J. N. (1999). Complexity of stability and controllability of elementary hybrid systems. Automatica, 35(3):479-489.
Blondel, V. D. and Tsitsiklis, J. N. (2000). A survey of computational complexity results in systems and control. Automatica, 36(9):1249-1274.
Blum, L., Cucker, F., Shub, M., and Smale, S. (1998). Complexity and Real Computation. Springer.
Blum, L., Shub, M., and Smale, S. (1989). On a theory of computation and complexity over the real numbers; NP completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21(1):1-46.
Bournez, O. (1999a). Achilles and the Tortoise climbing up the hyper-arithmetical hier-archy. Theoretical Computer Science, 210(1):21-71.
Bournez, O. (1999b). Complexité Algorithmique des Systèmes Dynamiques Continus et Hybrides. PhD thesis, Ecole Normale Supérieure de Lyon.
Bournez, O. (2006). How much can analog and hybrid systems be proved (super-)Turing. Applied Mathematics and Computation, 178(1):58-71.
Bournez, O., Campagnolo, M. L., Graça, D. S., and Hainry, E. (2007). Polynomial differential equations compute all real computable functions on computable compact intervals. Journal of Complexity. To appear.
Bournez, O. and Hainry, E. (2005). Elementarily computable functions over the real numbers and R-sub-recursive functions. Theoretical Computer Science, 348(2-3): 130-147.
Bournez, O. and Hainry, E. (2006). Recursive analysis characterized as a class of real recursive functions. Fundamenta Informaticae, 74(4):409-433.
Bouyer, P., Dufourd, C., Fleury, E., and Petit, A. (2000a). Are timed automata updatable? In Emerson, E. A. and Sistla, A. P., editors, Computer Aided Verification, 12th Interna-tional Conference, CAV 2000, Chicago, IL, July 15-19, 2000, Proceedings, volume 1855 of Lecture Notes in Computer Science, pages 464-479. Springer.
Bouyer, P., Dufourd, C., Fleury, E., and Petit, A. (2000b). Expressiveness of updatable timed automata. In Nielsen, M. and Rovan, B., editors, Mathematical Foundations of Computer Science 2000, 25th International Symposium, MFCS 2000, Bratislava, Slo-vakia, August 28 - September 1, 2000, Proceedings, volume 1893 of Lecture Notes in Computer Science, pages 232-242. Springer.
Bouyer, P. and Petit, A. (1999). Decomposition and composition of timed automata. In Wiedermann, J., van Emde Boas, P., and Nielsen, M., editors, Automata, Languages and Programming, 26th International Colloquium, ICALP’99, Prague, Czech Republic, July 11-15, 1999, Proceedings, volume 1644 of Lecture Notes in Computer Science, pages 210-219. Springer.
Bouyer, P. and Petit, A. (2002). A Kleene/Büchi-like theorem for clock languages. Jour-nal of Automata, Languages and Combinatorics, 7(2):167-186.
Bowles, M. D. (1996). U.S. technological enthusiasm and British technological skepticism in the age of the analog brain. IEEE Annals of the History of Computing, 18(4): 5-15.
Branicky, M. S. (1995a). Studies in Hybrid Systems: Modeling, Analysis, and Control. PhD thesis, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA.
Branicky, M. S. (1995b). Universal computation and other capabilities of hybrid and continuous dynamical systems. Theoretical Computer Science, 138(1):67-100.
Brihaye, T. (2006). A note on the undecidability of the reachability problem for o-minimal dynamical systems. Math. Log. Q, 52(2):165-170.
Brihaye, Th. and Michaux, Ch. (2005). On the expressiveness and decidability of o-minimal hybrid systems. Journal of Complexity, 21(4):447-478.
Brockett, R. W. (1989). Smooth dynamical systems which realize arithmetical and logical operations. In Nijmeijer, H. and Schumacher, J. M., editors, Three Decades of Mathemat-ical Systems Theory, volume 135 of Lecture Notes in Computer Science, pages 19-30. Springer.
Brockett, R. W. (1991). Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems. Linear Algebra and its Applications, 146:79-91.
Brockett, R. W. (1994). Dynamical systems and their associated automata. In U. Helmke, R. M. and Saurer, J., editors, Systems and Networks: Mathematical Theory and Applications, volume 77, pages 49-69. Akademi-Verlag, Berlin.
Bush, V. (1931). The differential analyser. Journal of the Franklin Institute, 212(4): 447-488.
Calude, C. S. and Pavlov, B. (2002). Coins, Quantum measurements, and Turing’s bar-rier. Quantum Information Processing, 1(1-2):107-127.
Campagnolo, M., Moore, C., and Costa, J. F. (2000). Iteration, inequalities, and differ-entiability in analog computers. Journal of Complexity, 16(4):642-660.
Campagnolo, M., Moore, C., and Costa, J. F. (2002). An analog characterization of the Grzegorczyk hierarchy. Journal of Complexity, 18(4):977-1000.
Campagnolo, M. L. (2001). Computational complexity of real valued recursive functions and analog circuits. PhD thesis, IST, Universidade Técnica de Lisboa.
Campagnolo, M. L. (2002). The complexity of real recursive functions. In Calude, C., Dinneen, M., and Peper, F., editors, Unconventional Models of Computation, UMC’02, Volume 2509 in Lecture Notes in Computer Science, pages 1-14. Springer.
Campagnolo, M. L. (2004). Continuous time computation with restricted integration capabilities. Theoretical Computer Science, 317(4):147-165.
Campagnolo, M. L. and Ojakian, K. (2007). The elementary computable functions over the real numbers: applying two new techniques. Archive for Mathematical Logic. To appear.
Casey, M. (1996). The dynamics of discrete-time computation, with application to re-current neural networks and finite state machine extraction. Neural Computation, 8: 1135-1178.
Casey, M. (1998). Correction to proof that recurrent neural networks can robustly recog-nize only regular languages. Neural Computation, 10:1067-1069.
Ceraens, K. and Viksna, J. (1996). Deciding reachability for planar multi-polynomial systems. In Hybrid Systems III, volume 1066 of Lecture Notes in Computer Science, page 389. Springer-Verlag.
Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics,, 58:345-363. Reprinted in [73].
Clote, P. (1998). Computational models and function algebras. In Griffor, E. R., editor, Handbook of Computability Theory, pages 589-681. North-Holland, Amsterdam.
Coddington, E. A. and Levinson, N. (1972). Theory of Ordinary Differentiel Equations. McGraw-Hill.
Collins, P. (2005). Continuity and computability on reachable sets. Theoretical Computer Science, 341:162-195.
Collins, P. and Lygeros, J. (2005). Computability of finite-time reachable sets for hybrid systems. In Proceedings of the 44th IEEE Conference on Decision and Control and the European Control Conference, pages 4688-4693. IEEE Computer Society Press.
Collins, P. and van Schuppen, J. H. (2004). Observability of piecewise-affine hybrid sys-tems. In Alur, R. and Pappas, G. J., editors, Hybrid Systems: Computation and Control, 7th International Workshop, HSCC 2004, Philadelphia, PA, March 25-27, 2004, Pro-ceedings, volume 2993 of Lecture Notes in Computer Science, pages 265-279. Springer.
Copeland, B. J. (1998). Even Turing machines can compute uncomputable functions. In Calude, C., Casti, J., and Dinneen, M., editors, Unconventional Models of Computations. Springer.
Copeland, B. J. (2002). Accelerating Turing machines. Minds and Machines, 12: 281-301.
Costa, J. F. and Mycka, J. (2006). The conjecture P = NP given by some analytic condition. In Bekmann, A., Berger, U., Löwe, B., and Tucker, J., editors, Logical Approaches to Computational Barriers, Second conference on Computability in Europe, CiE 2006, pages 47-57, Swansea, UK. Report CSR 7-26, Report Series, University of Wales Swansea Press, 2006.
Coward, D. (2006). Doug Coward’s Analog Computer Museum. http://dcoward best.vwh.net/analog/.
Davies, E. B. (2001). Building infinite machines. The British Journal for the Philosophy of Science, 52:671-682.
Dee, D. and Ghil, M. (1984). Boolean difference equations, I: Formulation and dynamic behavior. SIAM Journal on Applied Mathematics, 44(1):111-126.
Davis M. (ed.) (1965) The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, NY.
Delvenne, J.-C., Kurka, P., and Blondel, V. D. (2004). Computational universality in symbolic dynamical systems. In Margenstern, M., editor, MCU: International Confer-ence on Machines, Computations, and Universality, volume 3354 of Lecture Notes in Computer Science, pages 104-115. Springer.
Deutsch, D. (1985). Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society (London), Series A, 400:97-117.
Durand-Lose, J. (2005). Abstract geometrical computation: Turing-computing ability and undecidability. In Cooper, S. B., Löwe, B., and Torenvliet, L., editors, New Com-putational Paradigms, First Conference on Computability in Europe, CiE 2005, Amster-dam, The Netherlands, June 8-12, 2005, Proceedings, volume 3526 of Lecture Notes in Computer Science, pages 106-116. Springer.
Earman, J. and Norton, J. D. (1993). Forever is a day: Supertasks in Pitowksy and Malament-Hogarth spacetimes. Philosophy of Science, 60(1):22-42.
Etesi, G. and Németi, I. (2002). Non-Turing computations via Malament-Hogarth space-times. International Journal Theoretical Physics, 41:341-370.
Faybusovich, L. (1991a). Dynamical systems which solve optimization problems with linear constraints. IMA Journal of Mathematical Control and Information, 8:135-149.
Faybusovich, L. (1991b). Hamiltonian structure of dynamical systems which solve linear programming problems. Physics, D53:217-232.
Filippov, A. (1988). Differential equations with discontinuous right-hand sides. Kluwer Academic Publishers.
Finkel, O. (2006). On the shuffle of regular timed languages. Bulletin of the European Association for Theoretical Computer Science, 88:182-184. Technical Contributions.
Foy, J. (2004). A dynamical system which must be stable whose stability cannot be proved. Theoretical Computer Science, 328(3):355-361.
Francisco, A. P. L. (2002). Finite automata over continuous time. Diploma Thesis. Universidade Técnica de Lisboa, Instituto Superior Técnico.
Fränzle, M. (1999). Analysis of hybrid systems: An ounce of realism can save an infin-ity of states. In Flum, J. and Rodríguez-Artalejo, M., editors, Computer Science Logic (CSL’99), volume 1683 of Lecture Notes in Computer Science, pages 126-140. Springer Verlag.
Gori, M. and Meer, K. (2002). A step towards a complexity theory for analog systems. Mathematical Logic Quarterly, 48(Suppl. 1):45-58.
Graça, D. (2002). The general purpose analog computer and recursive functions over the reals. Master’s thesis, IST, Universidade Técnica de Lisboa.
Graça, D. S. (2004). Some recent developments on Shannon’s general purpose analog computer. Mathematical Logic Quarterly, 50(4-5):473-485.
Graça, D. S. and Costa, J. F. (2003). Analog computers and recursive functions over the reals. Journal of Complexity, 19(5):644-664.
Graça, D., Campagnolo, M., and Buescu, J. (2005). Robust simulations of Turing ma-chines with analytic maps and flows. In Cooper, B., Loewe, B., and Torenvliet, L., editors, Proceedings of CiE’05, New Computational Paradigms, volume 3526 of Lecture Notes in Computer Science, pages 169-179. Springer.
Graça, D. S., Campagnolo, M. L., and Buescu, J. (2007). Computability with polynomial differential equations. Advances in Applied Mathematics. To appear.
Graça, D. S., Zhong, N., and Buescu, J. (2006). Computability, noncomputability and undecidability of maximal intervals of IVPs. Transactions of the American Mathematical Society. To appear.
Grigorieff, S. and Margenstern, M. (2004). Register cellular automata in the hyperbolic plane. Fundamenta Informaticae, 1(61):19-27.
Gruska, J. (1997). Foundations of Computing. International Thomson Publishing.
Gupta, V., A., T., and Jagadeesan, R. (1997). Robust timed automata. In Maler, O., editor, Hybrid and Real-Time Systems, International Workshop. HART’97, Grenoble, France, March 26-28, 1997, Proceedings, volume 1201 of Lecture Notes in Computer Science, pages 331-345. Springer.
Head, T. (1987). Formal language theory and DNA: An analysis of the generative capac-ity of specific recombinant behaviors. Bulletin of Mathematical Biology, 49:737-759.
Helmke, U. and Moore, J. (1994). Optimization and Dynamical Systems. Communica-tions and Control Engineering Series. Springer Verlag, London.
Henzinger, T. A., Kopke, P. W., Puri, A., and Varaiya, P. (1998). What’s decidable about hybrid automata? Journal of Computer and System Sciences, 57(1):94-124.
Henzinger, T. A. and Raskin, J.-F. (2000). Robust undecidability of timed and hybrid systems. In Lynch, N. A. and Krogh, B. H., editors, Hybrid Systems: Computation and Control, Third International Workshop, HSCC 2000, Pittsburgh, PA, March 23-25, 2000, Proceedings, volume 1790 of Lecture Notes in Computer Science, pages 145-159. Springer.
Hirsch, M. W., Smale, S., and Devaney, R. (2003). Differential Equations, Dynamical Systems, and an Introduction to Chaos. Elsevier Academic Press.
Hogarth, M. (1994). Non-Turing computers and non-Turing computability. In Proceedings of the Philosophy of Science Association (PSA’94), volume 1, pages 126-138.
Hogarth, M. (1996). Predictability, Computability and Spacetime. PhD thesis, Sidney Sussex College, Cambridge.
Hogarth, M. (2006). Non-Turing computers are the new non-Eucliedean geometries. In Future Trends in Hypercomputation. Sheffield, 11-13 September 2006. Available for download on www.hypercomputation.net.
Hogarth, M. L. (1992). Does general relativity allow an observer to view an eternity in a finite time? Foundations of Physics Letters, 5:173-181.
Hopfield, J. J. (1984). Neural networks with graded responses have collective computational properties like those of two-state neurons. Proceedings of the National Academy of Sciences of the United States of America, 81:3088-3092.
Hopfield, J. J. and Tank, D. W. (1985). ‘Neural’ computation of decisions in optimization problems. Biological Cybernetics, 52:141-152.
Hoyrup, M. (2006). Dynamical systems: stability and simulability. Technical report, Département d’Informatique, ENS Paris.
Kempe, A. (1876). On a general method of describing plane curves of the n-th degree by linkwork. Proceedings of the London Mathematical Society, 7:213-216.
Kieu, T. D. (2004). Hypercomputation with quantum adiabatic processes. Theoretical Computer Science, 317(1-3):93-104.
Kleene, S. C. (1936). General recursive functions of natural numbers. Mathematical Annals, 112:727-742. Reprinted in [73].
Ko, K.-I. (1983). On the computational complexity of ordinary differential equations. Information and Control, 58(1-3):157-194.
Ko, K.-I. (1991). Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser, Boston.
Koiran, P. (2001). The topological entropy of iterated piecewise affine maps is uncomputable. Discrete Mathematics & Theoretical Computer Science, 4(2):351-356.
Koiran, P., Cosnard, M., and Garzon, M. (1994). Computability with low-dimensional dynamical systems. Theoretical Computer Science, 132(1-2):113-128.
Koiran, P. and Moore, C. (1999). Closed-form analytic maps in one and two dimensions can simulate universal Turing machines. Theoretical Computer Science, 210(1):217-223.
Korovina, M. V. and Vorobjov, N. (2004). Pfaffian hybrid systems. In Marcinkowski, J. and Tarlecki, A., editors, Computer Science Logic, 18th International Workshop, CSL 2004, 13th Annual Conference of the EACSL, Karpacz, Poland, September 20-24, 2004, Proceedings, volume 3210 of Lecture Notes in Computer Science, pages 430-441. Springer.
Korovina, M. V. and Vorobjov, N. (2006). Upper and lower bounds on sizes of finite bisimulations of Pfaffian hybrid systems. In Beckmann, A., Berger, U., Löwe, B., and Tucker, J. V., editors, Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006, Proceedings, volume 3988 of Lecture Notes in Computer Science, pages 267-276. Springer.
Kurganskyy, O. and Potapov, I. (2005). Computation in one-dimensional piecewise maps and planar pseudo-billiard systems. In Calude, C., Dinneen, M. J., Paun, G., Pérez-Jiménez, M. J., and Rozenberg, G., editors, Unconventional Computation, 4th Interna-tional Conference, UC 2005, Sevilla, Spain, October 3-7, 2005, Proceedings, volume 3699 of Lecture Notes in Computer Science, pages 169-175. Springer.
Lafferriere, G. and Pappas, G. J. (2000). O-minimal hybrid systems. Mathematics of Control, Signals, and Systems, 13:1-21.
Legenstein, R. and Maass, W. (2007). What makes a dynamical system computationally powerful? In Haykin, S., Principe, J. C., Sejnowski, T., and McWhirter, J., editors, New Directions in Statistical Signal Processing: From Systems to Brain, pages 127-154. MIT Press, Cambridge, MA.
Lipshitz, L. and Rubel, L. A. (1987). A differentially algebraic replacement theorem, and analog computability. Proceedings of the American Mathematical Society, 99(2): 367-372.
Lipton, R. J. (1995). DNA solution of hard computational problems. Science, 268: 542-545.
Loff, B. (2007). A functional characterisation of the analytical hierarchy. In Computability in Europe 2007: Computation and Logic in the Real World.
Loff, B., Costa, J. F., and Mycka, J. (2007a). Computability on reals, infinite limits and differential equations. Applied Mathematics and Computation. To appear.
Loff, B., Costa, J. F., and Mycka, J. (2007b). The new promise of analog computation. In Computability in Europe 2007: Computation and Logic in the Real World.
Maass, W. (1996a). Lower bounds for the computational power of networks of spiking neurons. Neural Computation, 8(1):1-40.
Maass, W. (1996b). On the computational power of noisy spiking neurons. In Touretzky, D., Mozer, M. C., and Hasselmo, M. E., editors, Advances in Neural Information Processing Systems, volume 8, pages 211-217. MIT Press, Cambridge, MA.
Maass, W. (1997a). A model for fast analog computations with noisy spiking neurons. In Bower, J., editor, Computational Neuroscience: Trends in research, pages 123-127.
Maass, W. (1997b). Networks of spiking neurons: the third generation of neural network models. Neural Networks, 10:1659-1671.
Maass, W. (1999). Computing with spiking neurons. In Maass, W. and Bishop, C. M., editors, Pulsed Neural Networks, pages 55-85. MIT Press, Cambridge, MA.
Maass, W. (2002). Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK, 8(1):32-36.
Maass, W. (2003). Computation with spiking neurons. In Arbib, M. A., editor, The Handbook of Brain Theory and Neural Networks, pages 1080-1083. MIT Press, Cambridge, MA. 2nd edition.
Maass, W. and Bishop, C. (1998). Pulsed Neural Networks. MIT Press, Cambridge, MA.
Maass, W., Joshi, P., and Sontag, E. D. (2007). Computational aspects of feedback in neural circuits. Public Library of Science Computational Biology, 3(1):1-20. e165.
Maass, W. and Natschläger, T. (2000). A model for fast analog computation based on unreliable synapses. Neural Computation, 12(7):1679-1704.
Maass, W. and Orponen, P. (1998). On the effect of analog noise in discrete-time analog computations. Neural Computation, 10(5):1071-1095.
Maass, W. and Ruf, B. (1999). On computation with pulses. Information and Computation, 148(2):202-218.
Maass, W. and Sontag, E. (1999). Analog neural nets with gaussian or other common noise distributions cannot recognize arbitrary regular languages. Neural Computation, 11(3):771-782.
MacLennan, B. J. (2001). Can differential equations compute? citeseer.ist. psu.edu/maclennan01can.html.
Mills, J. (1995). Programmable VLSI extended analog computer for cyclotron beam control. Technical Report 441, Indiana University Computer Science.
Mills, J. W., Himebaugh, B., Allred, A., Bulwinkle, D., Deckard, N., Gopalakrishnan, N., Miller, J., Miller, T., Nagai, K., Nakamura, J., Ololoweye, B., Vlas, R., Whitener, P., Ye, M., , and Zhang, C. (2005). Extended analog computers: A unifying paradigm for VLSI, plastic and colloidal computing systems. In Workshop on Unique Chips and Systems (UCAS-1). Held in conjunction with IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS05), Austin, Texas.
Müller, N. and Moiske, B. (1993). Solving initial value problems in polynomial time. In Proc. 22 JAIIO - PANEL ’93, Part 2, pages 283-293.
Moore, C. (1990). Unpredictability and undecidability in dynamical systems. Physical Review Letters, 64(20):2354-2357.
Moore, C. (1991). Generalized shifts: unpredictability and undecidability in dynamical systems. Nonlinearity, 4(3):199-230.
Moore, C. (1996). Recursion theory on the reals and continuous-time computation. Theoretical Computer Science, 162(1):23-44.
Moore, C. (1998a). Dynamical recognizers: real-time language recognition by analog computers. Theoretical Computer Science, 201(1-2):99-136.
Moore, C. (1998b). Finite-dimensional analog computers: Flows, maps, and recurrent neural networks. In Calude, C. S., Casti, J. L., and Dinneen, M. J., editors, Unconventional Models of Computation (UMC’98). Springer.
Murray, J. D. (2002). Mathematical Biology. I: An Introduction. Springer, third edition.
Mycka, J. and Costa, J. F. (2004). Real recursive functions and their hierarchy. Journal of Complexity, 20(6):835-857.
Mycka, J. and Costa, J. F. (2005). What lies beyond the mountains? Computational systems beyond the Turing limit. European Association for Theoretical Computer Science Bulletin, 85:181-189.
Mycka, J. and Costa, J. F. (2006). The P = NP conjecture in the context of real and complex analysis. Journal of Complexity, 22(2):287-303.
Mycka, J. and Costa, J. F. (2007). A new conceptual framework for analog computation. Theoretical Computer Science, 374:277-290.
Natschläger, T. and Maass, W. (2002). Spiking neurons and the induction of finite state machines. Theoretical Computer Science: Special Issue on Natural Computing, 287(1):251-265.
Németi, I. and Andréka, H. (2006). New physics and hypercomputation. In Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., and Stuller, J., editors, SOFSEM 2006: Theory and Practice of Computer Science, 32nd Conference on Current Trends in Theory and Prac-tice of Computer Science, Merín, Czech Republic, January 21-27, 2006, Proceedings, volume 3831 of Lecture Notes in Computer Science, page 63. Springer.
Németi, I. and Dávid, G. (2006). Relativistic computers and the Turing barrier. Applied Mathematics and Computation, 178:118-142.
Nicollin, X., Olivero, A., Sifakis, J., and Yovine, S. (1993). An approach to the description and analysis of hybrid systems. In Grossman, R. L., Nerode, A., Ravn, A. P., and Rischel, H., editors, Hybrid Systems, volume 736 of Lecture Notes in Computer Science, pages 149-178. Springer.
Omohundro, S. (1984). Modelling cellular automata with partial differential equations. Physica D, 10D(1-2):128-134.
Orponen, P. (1994). Computational complexity of neural networks: a survey. Nordic Journal of Computing, 1(1):94-110.
Orponen, P. (1996). The computational power of discrete Hopfield nets with hidden units. Neural Computation, 8(2):403-415.
Orponen, P. (1997). A survey of continuous-time computation theory. In Du, D.-Z. and Ko, K.-I., editors, Advances in Algorithms, Languages, and Complexity, pages 209-224. Kluwer Academic Publishers.
Orponen, P. and Šíma, J. (2000). A continuous-time Hopfield net simulation of discrete neural networks. In Proceedings of the 2nd International ICSC Symposium on Neural Computations (NC’2000), pages 36-42, Berlin, Germany. ICSC Academic Press, Wetaskiwin (Canada)
Papadimitriou, C. (2001). Algorithms, games, and the Internet. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing: Hersonissos, Crete, Greece, July 6-8, 2001, pages 749-753, New York, NY. ACM Press.
P ăun, G. (2002). Membrane Computing. An Introduction. Springer-Verlag, Berlin.
Post, E. (1946). A variant of a recursively unsolvable problem. Bulletin of the American Math. Soc., 52:264-268.
Pour-El, M. and Zhong, N. (1997). The wave equation with computable initial data whose unique solution is nowhere computable. Mathematical Logic Quarterly, 43(4):499-509.
Pour-El, M. B. (1974). Abstract computability and its relation to the general purpose analog computer (some connections between logic, differential equations and analog computers). Transactions of the American Mathematical Society, 199:1-28.
Pour-El, M. B. and Richards, J. I. (1979). A computable ordinary differential equation which possesses no computable solution. Annals of Mathematical Logic, 17:61-90.
Pour-El, M. B. and Richards, J. I. (1981). The wave equation with computable initial data such that its unique solution is not computable. Advances in Mathematics, 39: 215-239.
Pour-El, M. B. and Richards, J. I. (1989). Computability in Analysis and Physics.Springer.
Puri, A. (1998). Dynamical properties of timed automata. In Ravn, A. P. and Rischel, H., editors, Formal Techniques in Real-Time and Fault-Tolerant Systems, 5th International Symposium, FTRTFT’98, Lyngby, Denmark, September 14-18, 1998, Proceedings, vol-ume 1486 of Lecture Notes in Computer Science, pages 210-227. Springer.
Puri, A. and Varaiya, P. (1994). Decidability of hybrid systems with rectangular differ-ential inclusion. In Dill, D. L., editor, Computer Aided Verification, 6th International Conference, CAV ’94, Stanford, CA. June 21-23, 1994, Proceedings, volume 818 of Lec-ture Notes in Computer Science, pages 95-104. Springer.
Rabin, M. O. (1963). Probabilistic automata. Information and Control, 6(3):230-245.
Rabinovich, A. (2003). Automata over continuous time. Theoretical Computer Science, 300(1-3):331-363.
Rabinovich, A. M. and Trakhtenbrot, B. A. (1997). From finite automata toward hybrid systems (extended abstract). In Chlebus, B. S. and Czaja, L., editors, Fundamentals of Computation Theory, 11th International Symposium, FCT ’97, Kraków, Poland, September 1-3, 1997, Proceedings, volume 1279 of Lecture Notes in Computer Science, pages 411-422. Springer.
Rubel, L. A. (1989). A survey of transcendentally transcendental functions. American Mathematical Monthly, 96(9):777-788.
Rubel, L. A. (1993). The extended analog computer. Advances in Applied Mathematics, 14:39-50.
Ruohonen, K. (1993). Undecidability of event detection for ODEs. Journal of Information Processing and Cybernetics, 29:101-113.
Ruohonen, K. (1994). Event detection for ODEs and nonrecursive hierarchies. In Karhumäki, J. and Maurer, H., editors, Proceedings of the Colloquium in Honor of Arto Salomaa. Results and Trends in Theoretical Computer Science (Graz, Austria, June 10-11,1994), volume 812 of Lecture Notes in Computer Science, pages 358-371. Springer, Berlin.
Ruohonen, K. (1996). An effective Cauchy-Peano existence theorem for unique solutions. International Journal of Foundations of Computer Science, 7(2):151-160.
Ruohonen, K. (1997a). Decidability and complexity of event detection problems for ODEs. Complexity, 2(6):41-53.
Ruohonen, K. (1997b). Undecidable event detection problems for ODEs of dimension one and two. Theoretical Informatics and Applications, 31(1):67-79.
Ruohonen, K. (2004). Chomskian hierarchies of families of sets of piecewise continuous functions. Theory of Computing Systems, 37(5):609-638.
Shannon, C. E. (1941). Mathematical theory of the differential analyser. Journal of Mathematics and Physics MIT, 20:337-354.
Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. In Goldwasser, S., editor, Proceedings of the 35th Annual Symposium on Founda-tions of Computer Science, pages 124-134, Los Alamitos, CA. IEEE Computer Society Press.
Siegelmann, H. T. and Fishman, S. (1998). Analog computation with dynamical systems. Physica D, 120:214-235.
Siegelmann, H. T. and Sontag, E. D. (1994). Analog computation via neural networks. Theoretical Computer Science, 131(2):331-360.
Siegelmann, H. T. and Sontag, E. D. (1995). On the computational power of neural nets. Journal of Computer and System Sciences, 50(1):132-150.
Šíma and Orponen (2003a). Exponential transients in continuous-time Liapunov systems. Theoretical Computer Science, 306(1-3):353-372.
Šíma, J. and Orponen, P. (2003b). Continuous-time symmetric Hopfield nets are computationally universal. Neural Computation, 15(3):693-733.
Šíma, J. and Orponen, P. (2003c). General-purpose computation with neural networks: A survey of complexity theoretic results. Neural Computation, 15(12):2727-2778.
Smith, W. D. (1998). Plane mechanisms and the downhill principle. http:// citeseer.ist.psu.edu/475350.html.
Smith, W. D. (2006). Church’s thesis meets the N-body problem. Applied Mathematics and Computation, 178(1):154-183.
Stoll, H. M. and Lee, L. S. (1988). A continuous-time optical neural network. In IEEE Second International Conference on Neural Networks (2nd ICNN’88), volume II, pages 373-384, San Diego, CA. IEEE Society Press.
Svoboda, A. (1948). Computing Mechanisms and Linkages. McGraw Hill. Reprinted by Dover Publications in 1965.
Thomson, W. (1876). On an instrument for calculating the integral of the product of two given functions. In Proceedings of the Royal Society of London, volume 24, pages 266-276.
Trakhtenbrot, B. (1995). Origins and metamorphoses of the trinity: Logic, nets, automata. In Kozen, D., editor, Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science San Diego, CA, June 26-29, 1995, pages 506-507. IEEE Computer Society, Press.
Trakhtenbrot, B. A. (1999). Automata and their interaction: Definitional suggestions. In Ciobanu, G. and Paun, G., editors, Fundamentals of Computation Theory, 12th Interna-tional Symposium, FCT ’99, Iasi, Romania, August 30 - September 3, 1999, Proceedings, volume 1684 of Lecture Notes in Computer Science, pages 54-89. Springer.
Tucker, J. V. and Zucker, J. I. (2007). Computability of analog networks. Theoretical Computer Science, 371(1-2):115-146.
Turing, A. (1936). On computable numbers, with an application to the EntscheidungsproblemֶProceedings of the London Mathematical Society, 42(2):230-265. Reprinted in [73].
Vergis, A., Steiglitz, K., and Dickinson, B. (1986). The complexity of analog computation. Mathematics and Computers in Simulation, 28(2):91-113.
Weihrauch, K. (2000). Computable Analysis. Springer.
Weihrauch, K. and Zhong, N. (2002). Is wave propagation computable or can wave computers beat the Turing machine? Proceedings of the London Mathematical Society, 85 (3):312-332.
Welch, P. D. (2006). The extent of computation in Malament-Hogarth spacetimes. http://www.citebase.org/abstract?id=oai:arXiv.org:gr-qc/0609035.
Williams, M. R. (1996). About this issue. IEEE Annals of the History of Computing, 18(4).
Woods, D. and Naughton, T. J. (2005). An optical model of computation. Theoretical Computer Science, 334(1-3):227-258.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Bournez, O., Campagnolo, M.L. (2008). A Survey on Continuous Time Computations. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds) New Computational Paradigms. Springer, New York, NY. https://doi.org/10.1007/978-0-387-68546-5_17
Download citation
DOI: https://doi.org/10.1007/978-0-387-68546-5_17
Publisher Name: Springer, New York, NY
Print ISBN: 978-0-387-36033-1
Online ISBN: 978-0-387-68546-5
eBook Packages: Computer ScienceComputer Science (R0)