Deciding subspace reachability problems with application to Skolem's Problem
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915427495444480 |
|---|---|
| author | Everett, Samuel |
| author_facet | Everett, Samuel |
| contents | The higher-dimensional version of Kannan and Lipton's Orbit Problem asks whether it is decidable if a target subspace can be reached from a starting point under repeated application of a linear transformation. Similarly, the continuous analog of the Orbit Problem asks if a flow induced by a linear system of differential equations ever reaches some specified subspace. The decidability of both problems remains open, and in fact the problems generalize the discrete and continuous versions of Skolem's Problem. The object of this paper is to communicate a geometric perspective of the discrete and continuous Orbit Problems, alternate to the traditional and highly technical algebraic and number-theoretic approaches to the problem. We derive a simple decision procedure capable of deciding a certain class of instances of the Orbit Problem, and, as an application, we obtain alternate proofs to a number of results using elementary geometric arguments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06528 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deciding subspace reachability problems with application to Skolem's Problem Everett, Samuel Logic in Computer Science 11B37, 03D99, 68Q01 F.0; G.2.0 The higher-dimensional version of Kannan and Lipton's Orbit Problem asks whether it is decidable if a target subspace can be reached from a starting point under repeated application of a linear transformation. Similarly, the continuous analog of the Orbit Problem asks if a flow induced by a linear system of differential equations ever reaches some specified subspace. The decidability of both problems remains open, and in fact the problems generalize the discrete and continuous versions of Skolem's Problem. The object of this paper is to communicate a geometric perspective of the discrete and continuous Orbit Problems, alternate to the traditional and highly technical algebraic and number-theoretic approaches to the problem. We derive a simple decision procedure capable of deciding a certain class of instances of the Orbit Problem, and, as an application, we obtain alternate proofs to a number of results using elementary geometric arguments. |
| title | Deciding subspace reachability problems with application to Skolem's Problem |
| topic | Logic in Computer Science 11B37, 03D99, 68Q01 F.0; G.2.0 |
| url | https://arxiv.org/abs/2410.06528 |