Decision Problems for Linear Dynamical Systems

Jeudi 29 Sep 2016

Dynamical systems, both discrete and continuous, permeate vast areas of mathematics, physics, engineering, and computer science. In this talk, we consider a selection of natural decision problems for linear dynamical systems, such as reachability of a given hyperplane. Such problems have applications in a wide array of scientific areas, ranging from theoretical biology and software verification to quantum computing and statistical physics. Perhaps surprisingly, the study of decidability and complexity questions for linear dynamical systems involves techniques from a variety of mathematical fields, including analytic and algebraic number theory, Diophantine geometry, and real algebraic geometry. I will survey some of the known results as well as recent advances and open problems.