License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.49
URN: urn:nbn:de:0030-drops-119105
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11910/
D'Costa, Julian ;
Lefaucheux, Engel ;
Ouaknine, Joël ;
Worrell, James
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.
BibTeX - Entry
@InProceedings{dcosta_et_al:LIPIcs:2020:11910,
author = {Julian D'Costa and Engel Lefaucheux and Jo{\"e}l Ouaknine and James Worrell},
title = {{How Fast Can You Escape a Compact Polytope?}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {49:1--49:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-140-5},
ISSN = {1868-8969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11910},
URN = {urn:nbn:de:0030-drops-119105},
doi = {10.4230/LIPIcs.STACS.2020.49},
annote = {Keywords: Continuous linear dynamical systems, termination}
}
|
Keywords: |
|
Continuous linear dynamical systems, termination |
|
Collection: |
|
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.03.2020 |
