2026-07-22T14:05:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14473 2024-03-06T10:54:06Z ddc:004 open_access

On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets D'Costa, Julian Lefaucheux, Engel Neumann, Eike Ouaknine, Joël Worrell, James Discrete linear dynamical systems Program termination Compact semialgebraic sets Theory of the reals 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julian D'Costa and Engel Lefaucheux and Eike Neumann and Joël Ouaknine and James Worrell 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.33 urn:nbn:de:0030-drops-144734 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.33 eng https://creativecommons.org/licenses/by/4.0/legalcode