| Title | On the Polytope Escape Problem for Continuous Linear Dynamical Systems |
| Publication Type | Conference Paper |
| Year of Publication | 2017 |
| Authors | Ouaknine, Joel, Sousa-Pinto, Joao, Worrell, James |
| Conference Name | Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-4590-3 |
| Keywords | composability, continuous linear dynamical systems, Dynamical Systems, Metrics, orbit problem, pubcrawl, resilience, Resiliency |
| Abstract | The Polytope Escape Problem for continuous linear dynamical systems consists of deciding, given an affine function f:Rd -\textbackslashtextgreater Rd and a convex polytope P Rd, both with rational descriptions, whether there exists an initial point x0 in P such that the trajectory of the unique solution to the differential equation: *x(t)=f(x(t)) x 0= x0 is entirely contained in P. We show that this problem is reducible in polynomial time to the decision version of linear programming with real algebraic coefficients. The latter is a special case of the decision problem for the existential theory of real closed fields, which is known to lie between NP and PSPACE. Our algorithm makes use of spectral techniques and relies, among others, on tools from Diophantine approximation. |
| URL | http://doi.acm.org/10.1145/3049797.3049798 |
| DOI | 10.1145/3049797.3049798 |
| Citation Key | ouaknine_polytope_2017 |
On the Polytope Escape Problem for Continuous Linear Dynamical Systems