Journal article
The polytope-collision problem
- Abstract:
-
The Orbit Problem consists of determining, given a matrix $A\in\mathbb{R}^{d\times d}$ and vectors $x,y\in \mathbb{R}^d$, whether there exists $n\in \mathbb{N}$ such that $A^n=y$. This problem was shown to be decidable in a seminal work of Kannan and Lipton in the 1980s. Subsequently, Kannan and Lipton noted that the Orbit Problem becomes considerably harder when the target $y$ is replaced with a subspace of $\mathbb{R}^d$. Recently, it was shown that the problem is decidable for vector-space...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Funding
Bibliographic Details
- Publisher:
- Leibniz International Proceedings in Informatics Publisher's website
- Journal:
- 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) Journal website
- Publication date:
- 2017-07-01
- Acceptance date:
- 2017-04-14
- Source identifiers:
-
658320
Item Description
- Keywords:
- Pubs id:
-
pubs:658320
- UUID:
-
uuid:e870c1c8-f10b-4734-bcd6-2511be823a72
- Local pid:
- pubs:658320
- Deposit date:
- 2017-05-10
Terms of use
- Copyright holder:
- Almagor et al
- Copyright date:
- 2017
- Notes:
-
© Shaull Almagor, Joël Ouaknine, and James Worrell;
licensed under Creative Commons License CC-BY
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record