The Semialgebraic Orbit Problem
<p>The Semialgebraic Orbit Problem is a fundamental reachability question that arises in the analysis of discrete-time linear dynamical systems such as automata, Markov chains, recurrence sequences, and linear while loops. An instance of the problem comprises a dimension d in N, a square matri...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl
2019
|
| _version_ | 1826264199691501568 |
|---|---|
| author | Almagor, S Ouaknine, J Worrell, J |
| author_facet | Almagor, S Ouaknine, J Worrell, J |
| author_sort | Almagor, S |
| collection | OXFORD |
| description | <p>The Semialgebraic Orbit Problem is a fundamental reachability question that arises in the analysis of discrete-time linear dynamical systems such as automata, Markov chains, recurrence sequences, and linear while loops. An instance of the problem comprises a dimension d in N, a square matrix A in Q^{d x d}, and semialgebraic source and target sets S,T subseteq R^d. The question is whether there exists x in S and n in N such that A^nx in T. The main result of this paper is that the Semialgebraic Orbit Problem is decidable for dimension d <= 3. Our decision procedure relies on separation bounds for algebraic numbers as well as a classical result of transcendental number theory - Baker's theorem on linear forms in logarithms of algebraic numbers. We moreover argue that our main result represents a natural limit to what can be decided (with respect to reachability) about the orbit of a single matrix. On the one hand, semialgebraic sets are arguably the largest general class of subsets of R^d for which membership is decidable. On the other hand, previous work has shown that in dimension d=4, giving a decision procedure for the special case of the Orbit Problem with singleton source set S and polytope target set T would entail major breakthroughs in Diophantine approximation.</p> |
| first_indexed | 2024-03-06T20:03:56Z |
| format | Conference item |
| id | oxford-uuid:284757ea-d0b4-42b2-8b29-4f0deee03f39 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:03:56Z |
| publishDate | 2019 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:284757ea-d0b4-42b2-8b29-4f0deee03f392022-03-26T12:11:56ZThe Semialgebraic Orbit ProblemConference itemhttp://purl.org/coar/resource_type/c_5794uuid:284757ea-d0b4-42b2-8b29-4f0deee03f39Symplectic Elements at OxfordSchloss Dagstuhl2019Almagor, SOuaknine, JWorrell, J<p>The Semialgebraic Orbit Problem is a fundamental reachability question that arises in the analysis of discrete-time linear dynamical systems such as automata, Markov chains, recurrence sequences, and linear while loops. An instance of the problem comprises a dimension d in N, a square matrix A in Q^{d x d}, and semialgebraic source and target sets S,T subseteq R^d. The question is whether there exists x in S and n in N such that A^nx in T. The main result of this paper is that the Semialgebraic Orbit Problem is decidable for dimension d <= 3. Our decision procedure relies on separation bounds for algebraic numbers as well as a classical result of transcendental number theory - Baker's theorem on linear forms in logarithms of algebraic numbers. We moreover argue that our main result represents a natural limit to what can be decided (with respect to reachability) about the orbit of a single matrix. On the one hand, semialgebraic sets are arguably the largest general class of subsets of R^d for which membership is decidable. On the other hand, previous work has shown that in dimension d=4, giving a decision procedure for the special case of the Orbit Problem with singleton source set S and polytope target set T would entail major breakthroughs in Diophantine approximation.</p> |
| spellingShingle | Almagor, S Ouaknine, J Worrell, J The Semialgebraic Orbit Problem |
| title | The Semialgebraic Orbit Problem |
| title_full | The Semialgebraic Orbit Problem |
| title_fullStr | The Semialgebraic Orbit Problem |
| title_full_unstemmed | The Semialgebraic Orbit Problem |
| title_short | The Semialgebraic Orbit Problem |
| title_sort | semialgebraic orbit problem |
| work_keys_str_mv | AT almagors thesemialgebraicorbitproblem AT ouakninej thesemialgebraicorbitproblem AT worrellj thesemialgebraicorbitproblem AT almagors semialgebraicorbitproblem AT ouakninej semialgebraicorbitproblem AT worrellj semialgebraicorbitproblem |