Conference item
How fast can you escape a compact polytope?
- Abstract:
- The Continuous Polytope Escape Problem (CPEP) asks whether every trajectory of a linear differential equation initialised within a convex polytope eventually escapes the polytope. We provide a polynomial-time algorithm to decide CPEP for compact polytopes. We also establish a quantitative uniform upper bound on the time required for every trajectory to escape the given polytope. In addition, we establish iteration bounds for termination of discrete linear loops via reduction to the continuous case.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, 488.5KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.STACS.2020.49
- Publication website:
- https://stacs2020.sciencesconf.org/
Authors
- Publisher:
- Schloss Dagstuhl
- Host title:
- 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
- Pages:
- 49:1--49:11
- Series:
- Leibniz International Proceedings in Informatics (LIPIcs)
- Series number:
- 154
- Place of publication:
- Dagstuhl, Germany
- Publication date:
- 2020-02-27
- Acceptance date:
- 2019-12-20
- Event title:
- 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
- Event location:
- Montpellier, France
- Event website:
- https://stacs2020.sciencesconf.org/
- Event start date:
- 2020-03-10
- Event end date:
- 2020-03-13
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 978-3-95977-140-5
- Language:
-
English
- Keywords:
- Pubs id:
-
1084192
- Local pid:
-
pubs:1084192
- Deposit date:
-
2020-01-31
Terms of use
- Copyright holder:
- D’Costa et al.
- Copyright date:
- 2020
- Rights statement:
- © Julian D’Costa, Engel Lefaucheux, 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