Bounding the escape time of a linear dynamical system over a compact semialgebraic set
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 e...
| Główni autorzy: | , , , , |
|---|---|
| Format: | Conference item |
| Język: | English |
| Wydane: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2022
|
| Hasła przedmiotowe: |
| _version_ | 1826310887700430848 |
|---|---|
| author | D'Costa, J Lefaucheux, E Neumann, E Ouaknine, J Worrell, J |
| author_facet | D'Costa, J Lefaucheux, E Neumann, E Ouaknine, J Worrell, J |
| author_sort | D'Costa, J |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T08:00:08Z |
| format | Conference item |
| id | oxford-uuid:31269d8e-a11a-4e39-aef9-793845f40b0f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:00:08Z |
| publishDate | 2022 |
| publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:31269d8e-a11a-4e39-aef9-793845f40b0f2023-09-26T17:02:31ZBounding the escape time of a linear dynamical system over a compact semialgebraic setConference itemhttp://purl.org/coar/resource_type/c_5794uuid:31269d8e-a11a-4e39-aef9-793845f40b0fLogic and verificationTheory of computationEnglishSymplectic Elements Schloss Dagstuhl – Leibniz-Zentrum für Informatik2022D'Costa, JLefaucheux, ENeumann, EOuaknine, JWorrell, JWe 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. |
| spellingShingle | Logic and verification Theory of computation D'Costa, J Lefaucheux, E Neumann, E Ouaknine, J Worrell, J Bounding the escape time of a linear dynamical system over a compact semialgebraic set |
| title | Bounding the escape time of a linear dynamical system over a compact semialgebraic set |
| title_full | Bounding the escape time of a linear dynamical system over a compact semialgebraic set |
| title_fullStr | Bounding the escape time of a linear dynamical system over a compact semialgebraic set |
| title_full_unstemmed | Bounding the escape time of a linear dynamical system over a compact semialgebraic set |
| title_short | Bounding the escape time of a linear dynamical system over a compact semialgebraic set |
| title_sort | bounding the escape time of a linear dynamical system over a compact semialgebraic set |
| topic | Logic and verification Theory of computation |
| work_keys_str_mv | AT dcostaj boundingtheescapetimeofalineardynamicalsystemoveracompactsemialgebraicset AT lefaucheuxe boundingtheescapetimeofalineardynamicalsystemoveracompactsemialgebraicset AT neumanne boundingtheescapetimeofalineardynamicalsystemoveracompactsemialgebraicset AT ouakninej boundingtheescapetimeofalineardynamicalsystemoveracompactsemialgebraicset AT worrellj boundingtheescapetimeofalineardynamicalsystemoveracompactsemialgebraicset |