D. S. Graça and N. Zhong. Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines. To appear in the journal Computability.
Get: Published version or Preprint
R. Gozzi and D. S. Graça. Characterizing time computational complexity classes with polynomial differential equations. To appear in the journal Computability.
Get: Published version or Preprint
D. S. Graça and N. Zhong. Computing the exact number of periodic orbits for planar flows. Transactions of the American Mathematical Society, 375:5491-5538, 2022.
Get: Published version or Preprint
D. S. Graça and N. Zhong. The set of hyperbolic equilibria and of invertible zeros on the unit ball is computable. Theoretical Computer Science, 895:48-54, Elsevier, 2021.
Get: Published version or Preprint
D. S. Graça and N. Zhong. Computability of Differential Equations. In: Brattka V., Hertling P. (editors) Handbook of Computability and Complexity in Analysis, pages 71-99. Springer, 2021.
Get: Published version or Preprint
D. S. Graça and N. Zhong. Computability of Limit Sets for Two-Dimensional Flows.In: De Mol L., Weiermann A., Manea F., Fernández-Duque D. (editors) Connecting with Computability. CiE 2021. Lecture Notes in Computer Science, vol 12813. Springer, 2021.
Get: Published version or Preprint
D. S. Graça, C. Rojas, and N. Zhong. Computing geometric Lorenz attractors with arbitrary precision. Transactions of the American Mathematical Society, 370:2955-2970, 2018.
Get: Published version or Preprint
O. Bournez, D. S. Graça, and A. Pouly. Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length. Journal of the ACM, 64(6), ACM 2017.
Get: Published version or Preprint
O. Bournez, D. S. Graça, and A. Pouly. On the Functions Generated by the General Purpose Analog Computer. Information and Computation, 257:34-57, Elsevier 2017.
Get: Published version or Preprint
O. Bournez, D. S. Graça, and A. Pouly. Computing with Polynomial Ordinary Differential Equations. Journal of Complexity, 36:106-140, Elsevier 2016.
Get: Published version or Preprint
O. Bournez, D. S. Graça, and A. Pouly. Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length - The General Purpose Analog Computer and Computable Analysis are two efficiently equivalent models of computations. Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016). In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, D. Sangiorgi editors, volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 109:1-109:15, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Best paper award (Track B).
Get: Published version (free access)
A. Pouly and D. S. Graça. Computational complexity of solving polynomial differential equations over unbounded domains. Theoretical Computer Science, 626(2):67-82, Elsevier 2016.
Get: Published version (free access)
O. Bournez, D. S. Graça, A. Pouly. Rigorous numerical computation of polynomial differential equations over unbounded domains. Proceedings of the 6th International Conference on Mathematical Aspects of Computer and Information Sciences (MACIS 2015). In I. S. Kotsireas, S. M. Rump, C. K. Yap editors, volume 9582 of Lecture Notes in Computer Science, pages 469-473, Springer, 2016.
Get: Published version or Preprint
D. S. Graça and N. Zhong. An analytic system with a computable hyperbolic sink whose basin of attraction is non-computable. Theory of Computing Systems, 57(2):478-520, Springer 2015.
Get: Published version or Preprint
O. Bournez, D. S. Graça, A. Pouly, and N. Zhong. Computability and computational complexity of the evolution of nonlinear dynamical systems. Proceedings of the 9th Conference on Computability in Europe, CiE 2013: The Nature of Computation — Logic, Algorithms, Applications. In P. Bonizzoni, V. Brattka, B. Löwe editors, volume 7921 of Lecture Notes in Computer Science, pages 12-21, Springer, 2013.
Get: Published version or Preprint
D. S. Graça and A. Pouly. Computational complexity of adaptive methods for solving polynomial differential equations over unbounded domains. Proceedings of the 10th International Conference on Computability and Complexity in Analysis (CCA 2013). In M. Hoyrup, K.-I Ko, R. Rettinger, N. Zhong editors, pages 36-47, FernUniversität in Hagen, 2013.
Get: Preprint
O. Bournez, D. S. Graça, and A. Pouly. Turing machines can be efficiently simulated by the General Purpose Analog Computer. Proceedings of the 10th annual conference on Theory and Applications of Models of Computation (TAMC 2013). In FT-H. H. Chan, L. C. Lau, L. Trevisan editors, volume 7876 of Lecture Notes in Computer Science, pages 169-180, Springer, 2013.
Get: Published version or Preprint
O. Bournez, D. S. Graça, and E. Hainry. Computation with perturbed dynamical systems. Journal of Computer and System Sciences, 79(5):714-724, Elsevier 2013.
Get: Published version (free access)
D. S. Graça, N. Zhong, and J. Buescu. Computability, noncomputability, and hyperbolic systems. Applied Mathematics and Computation, 219(6): 3039–3054, Elsevier, 2012.
Get: Published version or Preprint
D. S. Graça, N. Zhong, and H. S. Dumas. The connection between computability of a nonlinear problem and its linearization: the Hartman-Grobman theorem revisited. Theoretical Computer Science, 457(26):101-110, Elsevier, 2012.
Get: Published version (free access)
O. Bournez, D. S. Graça, and A. Pouly. On the complexity of solving polynomial initial value problems. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation (ISSAC 2012), 2012.
Get: Preprint
D. S. Graça. Non-computability, unpredictability, and financial markets. Complexity, 17(6):24-30, Wiley, 2012.
Get: Published version or Preprint
O. Bournez, D. S. Graça, and A. Pouly. Solving analytic differential equations in polynomial time over unbounded domains. Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011). In F. Murlak and P. Sankowski, editors, volume 6907 of Lecture Notes in Computer Science ARCoSS (Advanced Research in Computing and Software Science), pages 170-181, Springer, 2011.
Get: Published version or Preprint
D. S. Graça and N. Zhong. Computability in planar dynamical systems. Natural Computing, 10(4):1295-1312, 2011.
Get: Published version or Preprint
J. Buescu, D. S. Graça, and N. Zhong. Computability and Dynamical Systems. In M. Peixoto, A. Pinto, and D. Rand, editors, "Dynamics and Games in Science I", Springer, pages 169-181, 2011.
Get: Published version or Preprint
O. Bournez, D. S. Graça, and E. Hainry. Robust computations with dynamical systems. Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010). In P. Hlinený and A. Kucera, editors, volume 6281 of Lecture Notes in Computer Science ARCoSS (Advanced Research in Computing and Software Science), pages 198-208, Springer, 2010.
Get: Published version or Preprint
D. S. Graça, J. Buescu, and M. L. Campagnolo. Computational bounds on polynomial differential equations. Applied Mathematics and Computation, 215(4):1375-1385, 2009.
Get: Published version or Preprint
D. S. Graça and N. Zhong. Computing Domains of Attraction for Planar Dynamics. In C. S. Calude, J. F. Costa, N. Dershowitz, E. Freire, and G. Rozenberg, editors, Proceedings of the 8th International Conference on Unconventional Computation (UC 2009), volume 5715 of Lecture Notes in Computer Science, pages 179-190. Springer, 2009.
Get: Published version or Preprint
P. Collins and D. S. Graça. Effective computability of solutions of differential inclusions - the ten thousand monkeys approach. Journal of Universal Computer Science, 15(6):1162-1185, 2009.
Get: Published version (free access)
D. S. Graça, N. Zhong, and J. Buescu. Computability, noncomputability and undecidability of maximal intervals of IVPs. Transactions of the American Mathematical Society, 361(6):2913-2927, 2009.
Get: Published version (free access)
P. Collins and D. S. Graça. Effective computability of solutions of ordinary differential equations - the thousand monkeys approach. Electronic Notes in Theoretical Computer Science, 221:103-114, 2008. Presented at the Fifth International Conference on Computability and Complexity in Analysis (CCA 2008).
Get: Published version (free access)
D. S. Graça, J. Buescu, and M. L. Campagnolo. Boundedness of the domain of definition is undecidable for polynomial odes. Electronic Notes in Theoretical Computer Science, 202:49-57, 2008. Proceedings of the 4th International Conference of Computability and Complexity in Analysis (CCA 2007).
Get: Published version (free access)
D. S. Graça, M. L. Campagnolo, and J. Buescu. Computability with polynomial differential equations. Advances in Applied Mathematics, 40(3):330-349, 2008.
Get: Published version (free access)
D. S. Graça. Computability and dynamical systems: A perspective. In Proceedings of the 26th Weak Arithmetics Days, pages 95-107. Universidad de Sevilla, 2008.
Get: Preprint
O. Bournez, M. L. Campagnolo, D. S. Graça, and E. Hainry. Polynomial differential equations compute all real computable functions on computable compact intervals. Journal of Complexity, 23:317-335, 2007.
Get: Published version (free access)
D. S. Graça. Computability with Polynomial Differential Equations. PhD thesis, IST, Universidade Técnica de Lisboa, 2007. Supervised by J. Buescu and M. L. Campagnolo.
Get: Published version
O. Bournez, M. L. Campagnolo, D. S. Graça, and E. Hainry. The General Purpose Analog Computer and Computable Analysis are two equivalent paradigms of analog computation. In J.-Y. Cai, S. B. Cooper, and A. Li, editors, Theory and Applications of Models of Computation TAMC'06, volume 3959 of Lecture Notes in Computer Science, pages 631-643. Springer, 2006.
Get: Published version or Preprint
D. S. Graça, N. Zhong, and J. Buescu. The ordinary differential equation defined by a computable function whose maximal interval of existence is non-computable. In G.Hanrot and P.Zimmermann, editors, Proceedings of the 7th Conference on Real Numbers and Computers (RNC 7), pages 33-40. LORIA/INRIA, 2006.
Get: Preprint
D. S. Graça, M. L. Campagnolo, and J. Buescu. Robust simulations of Turing machines with analytic maps and flows. In B. Cooper, B. Löwe, and L. Torenvliet, editors, Proceedings of CiE'05, New Computational Paradigms, volume 3526 of Lecture Notes in Computer Science, pages 169-179. Springer, 2005.
Get: Published version or Preprint
D. S. Graça. Some recent developments on Shannon's General Purpose Analog Computer. Mathematical Logic Quarterly, 50(4-5):473-485, 2004.
Get: Published version or Preprint
D. S. Graça. Computability via analog circuits. In V. Brattka, M. Schröder, K. Weihrauch, and N. Zhong, editors, Procs. International Conference on Computability and Complexity in Analysis, pages 229-240. FernUniversität in Hagen, 2003.
Get: Preprint
D. S. Graça and J. F. Costa. Analog computers and recursive functions over the reals. Journal of Complexity, 19(5):644-664, 2003.
Get: Published version (free access)
D. S. Graça. The general purpose analog computer and recursive functions over the reals Master's thesis, IST, Universidade Técnica de Lisboa, 2002. Supervised by J. F. Costa.
Get: Published version