Fundamental Algorithmic Problems and Challenges in Dynamical and Cyber-Physical Systems
Channel: ETAPS 2017
Date: 2017-05-09

FoSSaCS invited talk, given by Joël Ouaknine (MPI-SWS, Germany, and University of Oxford, UK).

Dynamical and cyber-physical systems, whose continuous evolution is subject to differential equations, permeate vast areas of engineering, physics, mathematics, and computer science. In this talk, I consider a selection of fundamental algorithmic problems for such systems, such as reachability, invariant synthesis, and controllability. Although the decidability and complexity of many of these problems are open, some partial and conditional results are known, occasionally resting on certain number-theoretic hypotheses such as Schanuel's conjecture. More generally, the study of algorithmic problems for dynamical and cyber-physical systems draws from an eclectic array of mathematical tools, ranging from Diophantine approximation to algebraic geometry. I will present a personal and select overview of the field and discuss areas of current active research.