The pseudo-reachability problem for diagonalisable linear dynamical systems
We study fundamental reachability problems on pseudo-orbits of linear dynamical systems. Pseudo-orbits can be viewed as a model of computation with limited precision and pseudo-reachability can be thought of as a robust version of classical reachability. Using an approach based on <i>o</i&g...
| Main Authors: | , , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2022
|
| _version_ | 1797110910208180224 |
|---|---|
| author | D'Costa, J Karimov, T Majumdar, R Ouaknine, J Salamati, M Worrell, J |
| author_facet | D'Costa, J Karimov, T Majumdar, R Ouaknine, J Salamati, M Worrell, J |
| author_sort | D'Costa, J |
| collection | OXFORD |
| description | We study fundamental reachability problems on pseudo-orbits of linear dynamical systems. Pseudo-orbits can be viewed as a model of computation with limited precision and pseudo-reachability can be thought of as a robust version of classical reachability. Using an approach based on <i>o</i>-minimality of R<sub>exp</sub> we prove decidability of the discrete-time pseudo-reachability problem with arbitrary semialgebraic targets for diagonalisable linear dynamical systems. We also show that our method can be used to reduce the continuous-time pseudo-reachability problem to the (classical) time-bounded reachability problem, which is known to be conditionally decidable. |
| first_indexed | 2024-03-07T08:01:22Z |
| format | Conference item |
| id | oxford-uuid:f9055e41-eb1c-492a-be3f-ef7671b34c75 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:01:22Z |
| publishDate | 2022 |
| publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:f9055e41-eb1c-492a-be3f-ef7671b34c752023-09-27T12:31:01ZThe pseudo-reachability problem for diagonalisable linear dynamical systemsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:f9055e41-eb1c-492a-be3f-ef7671b34c75EnglishSymplectic Elements Schloss Dagstuhl – Leibniz-Zentrum für Informatik2022D'Costa, JKarimov, TMajumdar, ROuaknine, JSalamati, MWorrell, JWe study fundamental reachability problems on pseudo-orbits of linear dynamical systems. Pseudo-orbits can be viewed as a model of computation with limited precision and pseudo-reachability can be thought of as a robust version of classical reachability. Using an approach based on <i>o</i>-minimality of R<sub>exp</sub> we prove decidability of the discrete-time pseudo-reachability problem with arbitrary semialgebraic targets for diagonalisable linear dynamical systems. We also show that our method can be used to reduce the continuous-time pseudo-reachability problem to the (classical) time-bounded reachability problem, which is known to be conditionally decidable. |
| spellingShingle | D'Costa, J Karimov, T Majumdar, R Ouaknine, J Salamati, M Worrell, J The pseudo-reachability problem for diagonalisable linear dynamical systems |
| title | The pseudo-reachability problem for diagonalisable linear dynamical systems |
| title_full | The pseudo-reachability problem for diagonalisable linear dynamical systems |
| title_fullStr | The pseudo-reachability problem for diagonalisable linear dynamical systems |
| title_full_unstemmed | The pseudo-reachability problem for diagonalisable linear dynamical systems |
| title_short | The pseudo-reachability problem for diagonalisable linear dynamical systems |
| title_sort | pseudo reachability problem for diagonalisable linear dynamical systems |
| work_keys_str_mv | AT dcostaj thepseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT karimovt thepseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT majumdarr thepseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT ouakninej thepseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT salamatim thepseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT worrellj thepseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT dcostaj pseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT karimovt pseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT majumdarr pseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT ouakninej pseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT salamatim pseudoreachabilityproblemfordiagonalisablelineardynamicalsystems AT worrellj pseudoreachabilityproblemfordiagonalisablelineardynamicalsystems |