Reachability problems for linear dynamical systems

The object of principal interest in this thesis is linear dynamical systems: deterministic systems which evolve under a linear operator. They are specified by an initial state set I, contained in ℝm, and a real m-by-m evolution matrix A. We distinguish two varieties of linear dynamical systems: discrete-time and continuous-time. In the discrete-time setting, the state x(n) of the system at time n for natural n is governed by the difference equation x(n)=Ax(n-1). Similarly, in the continuous case, the state x(t) at real, non-negative times t is determined by a system of first-order linear differential equations: x'(t) = Ax(t). In both cases, x(0) lies in I. Throughout this thesis, we will be interested in the Reachability Problem for linear dynamical systems, which may be formulated in a general way as follows: given a target set T contained in ℝm and a (discrete- or continuous-time) linear dynamical system specified by the evolution matrix A and the set of initial states I, determine whether for all x(0) in I, starting from x(0), the system will eventually be in a state which lies in T. In order to make the decision problem well-defined, one must first fix an admissible class of initial sets and, similarly, a class of target sets of interest. For the purposes of expressing the problem instance, it is also necessary to restrict the domain of the input data to a subset of the reals which may be represented effectively, such as the rational numbers or the algebraic numbers. As we vary the choice of domain, the types of initial and target sets under consideration and the discreteness of time, a rich landscape of decision problems emerges. The goal of the present thesis is to explore pointwise reachability problems, that is, reachability from a single initial state. Under the assumption that I consists of a single point in ℝm provided as part of the input data, we will study reachability to polyhedral targets, in the context of both discrete- and continuous-time linear dynamical systems. We prove both upper complexity bounds and hardness results, employing in the process a wide-ranging arsenal of techniques and mathematical tools. We rely on powerful number-theoretic results, such as Baker's Theorem on inhomogeneous linear forms of logarithms of algebraic numbers, Schanuel's Conjecture on the transcendence degree of certain field extensions of the rationals, and Kronecker's Theorem on simultaneous inhomogeneous Diophantine approximation. We draw interesting connections with the study of linear recurrence sequences and exponential polynomials, and relate pointwise reachability to open problems concerning the approximability by rationals of algebraic numbers and logarithms of algebraic numbers. Albeit a simple model, linear dynamical systems are of profound interest, both from a theoretical and a practical standpoint. Reachability problems for linear dynamical systems have recently elicited considerable attention, due to their frequent occurrence in practice and their deep and wide-ranging connections with other fascinating areas of study, such as problems on Markov chains (Akshay et al., 2015), quantum automata (Derksen et al., 2005), Lindenmayer systems (Salomaa and Soittola, 1978), linear loops (Braverman, 2006), linear recurrence sequences (Everest et al., 2003) and exponential polynomials (Bell et al., 2010).