The pseudo-Skolem Problem is decidable
We study fundamental decision problems on linear dynamical systems in discrete time. We focus on pseudo-orbits, the collection of trajectories of the dynamical system for which there is an arbitrarily small perturbation at each step. Pseudo-orbits are generalizations of orbits in the topological the...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2021
|
| _version_ | 1797099538306039808 |
|---|---|
| author | D'Costa, J Karimov, T Majumdar, R Ouaknine, J Salamati, M Soudjani, S Worrell, J |
| author_facet | D'Costa, J Karimov, T Majumdar, R Ouaknine, J Salamati, M Soudjani, S Worrell, J |
| author_sort | D'Costa, J |
| collection | OXFORD |
| description | We study fundamental decision problems on linear dynamical systems in discrete time. We focus on pseudo-orbits, the collection of trajectories of the dynamical system for which there is an arbitrarily small perturbation at each step. Pseudo-orbits are generalizations of orbits in the topological theory of dynamical systems. We study the pseudo-orbit problem, whether a state belongs to the pseudo-orbit of another state, and the pseudo-Skolem problem, whether a hyperplane is reachable by an ε-pseudo-orbit for every ε. These problems are analogous to the well-studied orbit problem and Skolem problem on unperturbed dynamical systems. Our main results show that the pseudo-orbit problem is decidable in polynomial time and the Skolem problem on pseudo-orbits is decidable. The former extends the seminal result of Kannan and Lipton from orbits to pseudo-orbits. The latter is in contrast to the Skolem problem for linear dynamical systems, which remains open for proper orbits. |
| first_indexed | 2024-03-07T05:25:11Z |
| format | Conference item |
| id | oxford-uuid:e04e6910-60d9-4eea-bcab-f1bb47f9a3d3 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T05:25:11Z |
| publishDate | 2021 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:e04e6910-60d9-4eea-bcab-f1bb47f9a3d32022-03-27T09:46:14ZThe pseudo-Skolem Problem is decidableConference itemhttp://purl.org/coar/resource_type/c_5794uuid:e04e6910-60d9-4eea-bcab-f1bb47f9a3d3EnglishSymplectic ElementsSchloss Dagstuhl - Leibniz-Zentrum für Informatik2021D'Costa, JKarimov, TMajumdar, ROuaknine, JSalamati, MSoudjani, SWorrell, JWe study fundamental decision problems on linear dynamical systems in discrete time. We focus on pseudo-orbits, the collection of trajectories of the dynamical system for which there is an arbitrarily small perturbation at each step. Pseudo-orbits are generalizations of orbits in the topological theory of dynamical systems. We study the pseudo-orbit problem, whether a state belongs to the pseudo-orbit of another state, and the pseudo-Skolem problem, whether a hyperplane is reachable by an ε-pseudo-orbit for every ε. These problems are analogous to the well-studied orbit problem and Skolem problem on unperturbed dynamical systems. Our main results show that the pseudo-orbit problem is decidable in polynomial time and the Skolem problem on pseudo-orbits is decidable. The former extends the seminal result of Kannan and Lipton from orbits to pseudo-orbits. The latter is in contrast to the Skolem problem for linear dynamical systems, which remains open for proper orbits. |
| spellingShingle | D'Costa, J Karimov, T Majumdar, R Ouaknine, J Salamati, M Soudjani, S Worrell, J The pseudo-Skolem Problem is decidable |
| title | The pseudo-Skolem Problem is decidable |
| title_full | The pseudo-Skolem Problem is decidable |
| title_fullStr | The pseudo-Skolem Problem is decidable |
| title_full_unstemmed | The pseudo-Skolem Problem is decidable |
| title_short | The pseudo-Skolem Problem is decidable |
| title_sort | pseudo skolem problem is decidable |
| work_keys_str_mv | AT dcostaj thepseudoskolemproblemisdecidable AT karimovt thepseudoskolemproblemisdecidable AT majumdarr thepseudoskolemproblemisdecidable AT ouakninej thepseudoskolemproblemisdecidable AT salamatim thepseudoskolemproblemisdecidable AT soudjanis thepseudoskolemproblemisdecidable AT worrellj thepseudoskolemproblemisdecidable AT dcostaj pseudoskolemproblemisdecidable AT karimovt pseudoskolemproblemisdecidable AT majumdarr pseudoskolemproblemisdecidable AT ouakninej pseudoskolemproblemisdecidable AT salamatim pseudoskolemproblemisdecidable AT soudjanis pseudoskolemproblemisdecidable AT worrellj pseudoskolemproblemisdecidable |