On the complexity of the Escape Problem for linear dynamical systems over compact semialgebraic sets

Conference item

We study the computational complexity of the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets, or equivalently the Termination Problem for affine loops with compact semialgebraic guard sets. Consider the fragment of the theory of the reals consisting of negation-free ∃ ∀-sentences without strict inequalities. We derive several equivalent characterisations of the associated complexity class which demonstrate its robustness and illustrate its expressive power. We show that the Compact Escape Problem is complete for this class.

Authors: D'Costa, J; Lefaucheux, E; Neumann, E; Ouaknine, J; Worrell, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
• Host title: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
• Journal: LIPIcs
• Volume: 202
• Article number: 33
• Publication date: 2021-08-18
• Acceptance date: 2021-06-29
• Event title: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
• Event location: Tallinn, Estonia
• Event website: https://compose.ioc.ee/mfcs/
• Event start date: 2021-08-23
• Event end date: 2021-08-27
• DOI: 10.4230/LIPIcs.MFCS.2021.33
• EISSN: 1868-8969
• ISBN: 978-3-95977-201-3
• Language: English
• Keywords: FFR; theory of the reals; discrete linear dynamical systems; compact semialgebraic sets; program termination