Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-24T11:11:56.708Z Has data issue: false hasContentIssue false
  • English
  • Français

Computable analysis with applications to dynamic systems

Published online by Cambridge University Press:  09 March 2020

Pieter Collins Open the ORCID record for Pieter Collins [Opens in a new window]
Pieter Collins*
Affiliation:
Department of Data Science and Knowledge Engineering, Maastricht University, Maastricht, The Netherlands
*
*Corresponding author. Email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Numerical computation is traditionally performed using floating-point arithmetic and truncated forms of infinite series, a methodology which allows for efficient computation at the cost of some accuracy. For most applications, these errors are entirely acceptable and the numerical results are considered trustworthy, but for some operations, we may want to have guarantees that the numerical results are correct, or explicit bounds on the errors. To obtain rigorous calculations, floating-point arithmetic is usually replaced by interval arithmetic and truncation errors are explicitly contained in the result. We may then ask the question of which mathematical operations can be implemented in a way in which the exact result can be approximated to arbitrary known accuracy by a numerical algorithm. This is the subject of computable analysis and forms a theoretical underpinning of rigorous numerical computation. The aim of this article is to provide a straightforward introduction to this subject that is powerful enough to answer questions arising in dynamic system theory.

Keywords

Computable analysisTuring machinedynamic system
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 30 , Issue 2 , February 2020 , pp. 173 - 233
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s) 2020. Published by Cambridge University Press

References

Aberth, O. (2007). Introduction to Precise Numerical Methods, 2nd edn., Amsterdam, Elsevier/Academic Press. With 1 CD-ROM (Windows).Google Scholar
Ariadne: A C++ library for formal verification of cyber-physical systems, using reachability analysis for nonlinear hybrid automata (Release 1.9, 2018). http://www.ariadne-cps.org/.Google Scholar
Asarin, E., Bournez, O., Dang, T., Maler, O. and Pnueli, A. (2000). Effective synthesis of switching controllers for linear systems. Proceedings of the IEEE 88 1011–1025.CrossRefGoogle Scholar
Asarin, E., Maler, O. and Pnueli, A. (1995). Reachability analysis of dynamical systems having piecewise-constant derivatives. Theoretical Computer Science 138 (1) 35–65.CrossRefGoogle Scholar
Aubin, J.-P. and Cellina, A. (1984). Differential Inclusions, Grundlehren der Mathematischen Wissenschaften, vol. 264, Berlin, Springer-Verlag.CrossRefGoogle Scholar
Aubin, J.-P., Lygeros, J., Quincampoix, M. and Sastry, S. (2002). Impulse differential inclusions: a viability approach to hybrid systems. IEEE Transactions on Automatic Control 47 (1) 2–20.CrossRefGoogle Scholar
Battenfeld, I. (2008). Topological Domain Theory. Phd thesis, University of Edinburgh.Google Scholar
Battenfeld, I., Schröder, M. and Simpson, A. (2007). A convenient category of domains. In: Cardelli, L., Fiore, M. and Winskel, G. (eds.) Computation, Meaning, and Logic: Articles dedicated to Gordon Plotkin, Electronic Notes in Theoretical Computer Science, vol. 172, Amsterdam, Elsevier, 69–99.Google Scholar
Bauer, A. (2000). The Realizability Approach to Computable Analysis and Topology. Phd thesis, Carnegie Mellon University.Google Scholar
Beggs, E. J. and Tucker, J. V. (2009). Computations via Newtonian and relativistic kinematic systems. Applied Mathematics and Computation 215 (4) 1311–1322.CrossRefGoogle Scholar
Bishop, E. and Bridges, D. (1985). Constructive Analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 279, Berlin, Springer-Verlag.CrossRefGoogle Scholar
Blanck, J. (2000). Domain representations of topological spaces. Theoretical Computer Science 247 (1—2) 229–255.CrossRefGoogle Scholar
Blondel, V. D. and Tsitsiklis, J. N. (2000). The boundedness of all products of a pair of matrices is undecidable. Systems & Control Letters 41 (2) 135–140.CrossRefGoogle Scholar
Bournez, O., Campagnolo, M. L., Graça, D. S. and Hainry, E.. (2006). The general purpose analog computer and computable analysis are two equivalent paradigms of analog computation. In: Cai, J.-Y., Barry Cooper, S. and Li, A. (eds.) Proceedings of the Third International Conference on Theory and Applications of Models of Computation (TAMC), Springer, 631–643.CrossRefGoogle Scholar
Bournez, O., Graça, D. S. and Pouly, A. (2013). Turing machines can be efficiently simulated by the general purpose analog computer. In: Hubert Chan, T.-H., Lau, L. C. and Trevisan, L. (eds.) Theory and Applications of Models of Computation, Springer, 169–180.CrossRefGoogle Scholar
Brattka, V. (1998). Recursive and Computable Operations over Topological Structures. Phd thesis, FernUniversität Hagen.Google Scholar
Brattka, V., Hertling, P. and Weihrauch, K. (2008). A tutorial on computable analysis. In: Barry Cooper, S., Löwe, B. and Sorbi, A. (eds.) New Computational Paradigms: Changing Conceptions of What is Computable, New York, NY, Springer, 425–491.CrossRefGoogle Scholar
Brattka, V. and Presser, G. (2003). Computability on subsets of metric spaces. Theoretical Computer Science 305 43–76.CrossRefGoogle Scholar
Bresolin, D., Geretti, L., Villa, T. and Collins, P. (2015). An introduction to the verification of hybrid systems using Ariadne. In: Jan van Schuppen, H. and Villa, T. (eds.) Coordination Control of Distributed Systems, Lecture Notes in Control and Information Sciences, vol. 456, Cham, Springer International, 339–346.Google Scholar
Clementino, M. M., Giuli, E. and Tholen, W. (2004). A functional approach to general topology. In: Pedicchio, M. C. and Tholen, W. (eds.) Categorical Foundations, Encyclopedia of Mathematics and its Applications, vol. 97, Cambridge, Cambridge University Press, 103–163.Google Scholar
Collins, P. (2005). Continuity and computability of reachable sets. Theoretical Computer Science 341 (1–3) 162–195.CrossRefGoogle Scholar
Collins, P. (2007). Optimal semicomputable approximations to reachable and invariant sets. Theory of Computing Systems 41 (1) 33–48.CrossRefGoogle Scholar
Collins, P. (2008). Computability of controllers for discrete-time semicontinuous systems. In: Proceedings of the 18th International Symposium on the Mathematical Theory of Networks and Systems, Blacksburg, Virginia.Google Scholar
Collins, P. (2011). Semantics and computability of the evolution of hybrid systems. SIAM Journal on Control and Optimization 49 (2) 890–925.CrossRefGoogle Scholar
Collins, P. (2014). Computable stochastic processes. arXiv:1409.4667.Google Scholar
Collins, P. and Graça, D. (2008). Effective computability of solutions of ordinary differential equations — the thousand monkeys approach. In: Proceedings of the 5th International Conference on Computability and Complexity in Analysis (CCA’08), Electronic Notes in Theoretical Computer Science, Amsterdam, The Netherlands, Elsevier, 53–64.CrossRefGoogle Scholar
Collins, P. and Graça, D. S. (2009) Effective computability of solutions of differential inclusions: the ten thousand monkeys approach. J.UCS 15 (6) 1162–1185.Google Scholar
Dahlgren, F. (2007). Partial continuous functions and admissible domain representations. Journal of Logic and Computation 17 (6) 1063–1081.CrossRefGoogle Scholar
Daniel, J. W. and Moore, R. E. (1970). Computation and Theory in Ordinary Differential Equations, San Francisco, W. H. Freeman & Co Ltd.Google Scholar
Edalat, A. (2009). A computable approach to measure and integration theory. Information and Computation 207 (5) 642–659.CrossRefGoogle Scholar
Edalat, A. and Sünderhauf, P. (1999). A domain-theoretic approach to computability on the real line. Theoretical Computer Science 210 (1) 73–98.CrossRefGoogle Scholar
Engelking, R. (1989). General Topology, Sigma Series in Pure Mathematics, vol. 6, Berlin, Heldermann.Google Scholar
Ershov, Ju. L. (1973). Theorie der numerierungen i. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 19 (4) 289–388.CrossRefGoogle Scholar
Ershov, Ju. L. (1975). Theorie der numerierungen ii. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 21 (6) 473–584.CrossRefGoogle Scholar
Ershov, Ju. L. (1977). Theorie der numerierungen iii. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 23 (4) 289–371.Google Scholar
Escardó, M. (2004). Synthetic topology of data types and classical spaces. Electronic Notes in Theoretical Computer Science 87 21–156.Google Scholar
Escardó, M. and Heckmann, R. (2002). Topologies on spaces of continuous functions. Topology Proceedings 26 (2) 545–564.Google Scholar
Escardó, M., Lawson, J. and Simpson, A. (2004). Comparing Cartesian closed categories of (core) compactly generated spaces. Topology and its Applications 143 (1–3) 105–145.CrossRefGoogle Scholar
Filippov, A. F. (1988). Differential Equations with Discontinuous Righthand Sides, Mathematics and Its Applications, Dordrecht, Kluwer Academic Publishers.CrossRefGoogle Scholar
Franklin, S. P. (1965). Spaces in which sequences suffice. Fundamenta Mathematicae 57 (1) 107–115.CrossRefGoogle Scholar
Fränzle, M. (1999). Analysis of hybrid systems: an ounce of realism can save an infinity of states. In: Flum, J. and Rodriguez-Artalejo, M. (eds.) Computer Science Logic, Lecture Notes in Computer Science, vol. 1683, Berlin, Heidelberg, New York, Springer-Verlag.Google Scholar
Gabor, G. (2007). Continuous selection of the solution map for one-sided Lipschitz differential inclusions. Nonlinear Analysis 66 (5) 1185–1197.CrossRefGoogle Scholar
Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M. W. and Scott, D. S. (1980). A Compendium of Continuous Lattices, Berlin, Springer-Verlag.CrossRefGoogle Scholar
Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M. and Scott, D. S. (2003). Continuous Lattices and Domains, Encyclopedia of Mathematics and its Applications, vol. 93, Cambridge, Cambridge University Press.CrossRefGoogle Scholar
Goebel, R. and Teel, A. R. (2006). Solutions to hybrid inclusions via set and graphical convergence with stability theory applications. Automatica - A Journal of IFAC 42 (4) 573–587.CrossRefGoogle Scholar
Grzegorczyk, A. (1957). On the definitions of computable real continuous functions. Fundamenta Mathematicae 44 44–61.CrossRefGoogle Scholar
Hansen, E. and William Walster, G. (2004). Global Optimization using Interval Analysis, 2nd edn., Monographs and Textbooks in Pure and Applied Mathematics, vol. 264, New York, Marcel Dekker Inc.Google Scholar
Hauck, J. (1980). Konstruktive Darstellungen in topologischen Räumen mit rekursiver Basis. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 26 565–576.CrossRefGoogle Scholar
Hauck, J. (1981). Berechenbarkeit in topologischen Räumen mit rekursiver Basis. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 27 473–480.CrossRefGoogle Scholar
Hertling, P. (1999). A real number structure that is effectively categorical. Mathematical Logic Quarterly 45 (2) 147–182.CrossRefGoogle Scholar
Hofmann, K. H. and Lawson, J. D. (1978). The spectral theory of distributive continuous lattices. Transactions of the American Mathematical Society 246 285–310.CrossRefGoogle Scholar
Hofmann, K. and Mislove, M. (1981). Local compactness and continuous lattices. In: Continuous Lattices, vol. 871, Lecture Notes in Mathematics, Berlin, Heidelberg, Springer, 209–248.CrossRefGoogle Scholar
Isbell, J. R. (1975). Function spaces and adjoints. Mathematica Scandinavica 36 317–339.CrossRefGoogle Scholar
Jaulin, L., Kieffer, M., Didrit, O. and Walter, É. (2001). Applied Interval Analysis, London, Springer-Verlag London Ltd. With examples in parameter and state estimation, robust control and robotics, With 1 CD-ROM (UNIX, Sun Solaris).Google Scholar
Johnstone, P. T. (2002a). Sketches of an Elephant: a Topos Theory Compendium. Volume 1, Oxford Logic Guides, vol. 43. New York, The Clarendon Press, Oxford University Press.Google Scholar
Johnstone, P. T. (2002b). Sketches of an Elephant: a Topos Theory Compendium. Volume 2, Oxford Logic Guides, vol. 44, Oxford, The Clarendon Press, Oxford University Press.Google Scholar
Katok, A. and Hasselblatt, B. (1995). Introduction to the Modern Theory of Dynamical Systems, Encyclopedia of Mathematics and its Applications, vol. 54. Cambridge, Cambridge University Press.CrossRefGoogle Scholar
Keimel, K. and Paseka, J. (1994). A direct proof of the Hofmann-Mislove theorem. Proceedings of the American Mathematical Society 120 (1) 301–303.CrossRefGoogle Scholar
Kleene, S. C. (1936). General recursive functions of natural numbers. Mathematische Annalen 112 (1) 727–742.CrossRefGoogle Scholar
Ko, K.-I. (1991). Complexity Theory of Real Functions, Progress in Theoretical Computer Science, Boston, MA, Birkhäuser Boston Inc.CrossRefGoogle Scholar
Kushner, B. A. (1999). Markov’s constructive analysis; a participant’s view. Theoretical Computer Science 219 (1–2) 267–285. Computability and complexity in analysis (Castle Dagstuhl, 1997).CrossRefGoogle Scholar
Luckhardt, H. (1977). A fundamental effect in computations on real numbers. Theoretical Computer Science 5 (3) 321–324.CrossRefGoogle Scholar
Martin-Löf, P. (1984). Intuitionistic Type Theory, Napoli, Bibliopolis.Google Scholar
Mazur, S. (1963). Computable Analysis, Razprawy Matematyczne, vol. 33, Warszawa, Państwowe Wydawnictwo Naukowe.Google Scholar
Moore, R. E., Baker Kearfott, R. and Cloud, M. J. (2009). Introduction to Interval Analysis, Philadelphia, PA, Society for Industrial and Applied Mathematics (SIAM).CrossRefGoogle Scholar
O’Connor, R. and Spitters, B. (2010). A computer-verified monadic functional implementation of the integral. Theoretical Computer Science 411 (37) 3386–3402.CrossRefGoogle Scholar
Pauly, A. (2016). On the topological aspects of the theory of represented spaces. Computability 5 (2) 159–180.CrossRefGoogle Scholar
Pauly, A. and de Brecht, M. (2015). Descriptive set theory in the category of represented spaces. In: Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE, 438–449.CrossRefGoogle Scholar
Pour-El, M. B. and Ian Richards, J. (1989). Computability in Analysis and Physics, Perspectives in Mathematical Logic, Berlin, Springer-Verlag.CrossRefGoogle Scholar
Puri, A., Varaiya, P. and Borkar, V. (1996). Epsilon-approximation of differential inclusions. In: Alur, R., Henzinger, T. A. and Sontag, E. D. (eds.) Hybrid Systems III, LNCS, vol. 1066, Berlin, Springer, 362–376.CrossRefGoogle Scholar
Ruohonen, K. (1996). An effective Cauchy-Peano existence theorem for unique solutions. International Journal of Foundations of Computer Science 7 (2) 151–160.CrossRefGoogle Scholar
Saint-Pierre, P. (1994). Approximation of the viability kernel. Applied Mathematics & Optimization 29 (2) 187–209.CrossRefGoogle Scholar
Schröder, M. (2002a). Admissible Representations for Continuous Computations. Phd thesis, Fachbereich Informatik, FernUniversitöt Hagen.Google Scholar
Schröder, M. (2002b). Extended admissibility. Theoretical Computer Science 284 (2) 519–538. Computability and complexity in analysis (Castle Dagstuhl, 1999).CrossRefGoogle Scholar
Sipser, M. (1996). Introduction to the Theory of Computation, Boston, Course Technology, International Thomson.CrossRefGoogle Scholar
Steen, L. A. and Seebach, J. A. (1978). Counterexamples in Topology, 2nd edn., New York, Springer-Verlag.CrossRefGoogle Scholar
Taylor, P. (2008). A lambda calculus for real analysis. http://www.monad.me.uk/.Google Scholar
Tomlin, C., Lygeros, J. and Sastry, S. (2000). A game theoretic approach to controller design for hybrid systems. Proceedings of the IEEE 88 (7), 949–970.CrossRefGoogle Scholar
Turing, A. M. (1937) On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society (2) 43 (1) 230–265.CrossRefGoogle Scholar
Troelstra, A. S. and van Dalen, D. (1988). Constructivism in Mathematics: An Introduction, Volume 1, Studies in Logic and the Foundations of Mathematics, vol. 121, Amsterdam, North-Holland.Google Scholar
van Stigt, W. P. (1990). Brouwer’s Intuitionism, Studies in the History and Philosophy of Mathematics, vol. 2, Amsterdam, North-Holland Publishing Co.Google Scholar
Vickers, S. (1989). Topology via Logic, Cambridge Tracts in Theoretical Computer Science, vol. 5, Cambridge, Cambridge University Press.Google Scholar
Weihrauch, K. (2000). Computable Analysis: An Introduction, Texts in Theoretical Computer Science. An EATCS Series, Berlin, Springer-Verlag.CrossRefGoogle Scholar
Weihrauch, K. and Grubba, T. (2009). Elementary computable topology. J.UCS 15 (6) 1381–1422.Google Scholar
Ziegler, M. (2009). Physically-relativized Church-Turing Hypotheses: physical foundations of computing and complexity theory of computational physics. Applied Mathematics and Computation 215 (4) 1431–1447.CrossRefGoogle Scholar