| Summary: | <p>In this thesis we explore decision problems for linear dynamical systems, which are a fundamental model in theoretical computer science, software verification and control theory. We focus on the reachability and escape problems in discrete and continuous linear dynamical systems, and their generalizations to pseudo-orbits, which are a model of computation with limited precision.</p>
<p>We consider the problem of deciding whether a finitely generated matrix semigroup contains a non-negative matrix, and show that it is decidable subject to Schanuel’s conjecture when the matrices commute, and unde- cidable in general. We show unconditional decidability of eventual non- negativity for a single matrix, solving a problem posed by S. Akshay.</p>
<p>In the setting of discrete pseudo-orbits, we show that the analogues of the classical orbit and Skolem problems are decidable. For diagonalisable linear dynamical systems, we show that the pseudo-reachability problem is decidable for arbitrary semialgebraic targets. We show that the similar robust reachability problem is decidable in full generality. For continuous pseudo-orbits, we show the same results assuming Schanuel’s conjecture.</p>
<p>Finally, we establish a uniform upper bound on the number of iterations it takes for every orbit of a matrix to escape a compact semialgebraic set. For a rational matrix and set defined over rational data, the bound is doubly exponential in the dimension, and singly exponential in the rest of the data. We show that this bound is tight by providing a matching lower bound.</p>
|
|---|