Daniel S. Graça
Email: dgraca[at]ualg[dot]pt
Current affiliations
Research topics
- Dynamical systems and computation
- Computability questions related to the evolution of dynamical systems: this is research on the limits of what can theoretically be inferred about dynamical systems using algorithms - it can be proved mathematically that some problems about dynamical systems cannot be solved with algorithms, no matter how clever the algorithms are or how many computational resources are used to run these algorithms.
- Computational complexity questions related to the evolution of dynamical systems: this is research on the limits of what can theoretically be inferred, using a reasonable amount of computational resources (time, etc.), about dynamical systems using algorithms. Some problems are "computationally intractable" in the sense that they are theoretically solvable, although in practice any algorithm solving them is so expensive from a computational point of view that the problem is in general "unsolvable" from a practical point of view. This is often due to the inherent "computational complexity" of the underlying problem. The idea is to try to understand which features these "untractable" problems have that distinguish them from "easier" problems. This is central question in the "P vs NP" millenium problem from the Clay Mathematics Institute.
- Verification of properties involving dynamical systems: in many applications one is interested in the following type of problem: to rigourously (i.e. using a mathematical sound approach) verify that some dynamical system is always "safe" (e.g. we may want to verify that an airplane will never fall due to a software problem, or that two trains will never collide) using a computational approach, since many systems are so complex that it is humanely impossible to verify them by "hand". Since some problems are not computationally solvable, in verification one is interested in understanding which properties can be automatically verified.
- Models of computation over continuous spaces
- Computable analysis: it studies mathematical analysis and continuous structures in general using a computability perspective, to understand which processes are computable. To achieve this objective continuous objects (real numbers, real functions, sets, etc.) are coded, for example, as infinite (Cauchy) sequences, etc., and computation is done over these sequences using a discrete (digital) model of computation.
- Analog computation/Shannon's General Purpose Analog Computer (GPAC): in this setting computation is done directly by a model of computation (the GPAC) introduced by Claude Shannon that uses ordinary differential equations to compute. This model can be implement in practice, for example, using analog electronics. Here we aim to understand what is the computational power of such models (compared to the digital paradigm) and whether such models are more well-suited for some tasks. We have for example shown that the GPAC can simulate Turing machines and that computable analysis are equivalent from a computability perspective and that the GPAC can simulate the standard model of discrete computation (Turing machines).
- Polynomial ordinary differential equations as models of computation: solutions of ordinary differential equations defined with the standard functions of analysis (polynomials, trigonometric functions, exponentials, etc.) can always be rewritten as solutions of polynomial ordinary differential equations. Here we are interested in understanding the computational power of such models which are equivalent to Shannon's GPAC.
- Characterization of complexity classes using continuous models: recently we were able to characterize classical (discrete) computational complexity classes such as P (from the "P vs NP" problem mentioned above) or PSPACE using a purely continuous characterization involving only polynomial ordinary differential equations. The idea here is trying to understand up to which point such characterizations can be made.
Other activities
Recent news
Projects
- Computing with Infinite Data (Marie Curie RISE project financed via Horizon 2020 by the European Union). This projects involves 20 institutions from several countries.
Publications
