2026-07-22T11:40:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16837 2024-03-06T10:58:27Z ddc:004 open_access

Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set D'Costa, Julian Lefaucheux, Engel Neumann, Eike Ouaknine, Joël Worrell, James Discrete linear dynamical systems Program termination Compact semialgebraic sets Uniform termination bounds We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for every orbit of a rational matrix to escape a compact semialgebraic set defined over rational data. Our bound is doubly exponential in the ambient dimension, singly exponential in the degrees of the polynomials used to define the semialgebraic set, and singly exponential in the bitsize of the coefficients of these polynomials and the bitsize of the matrix entries. We show that our bound is tight by providing a matching lower bound. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julian D'Costa and Engel Lefaucheux and Eike Neumann and Joël Ouaknine and James Worrell 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.39 urn:nbn:de:0030-drops-168374 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.39 eng https://creativecommons.org/licenses/by/4.0/legalcode