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: https://drops.dagstuhl.de/opus/volltexte/2020/11910/
Go to the corresponding LIPIcs Volume Portal


D'Costa, Julian ; Lefaucheux, Engel ; Ouaknine, Joël ; Worrell, James

How Fast Can You Escape a Compact Polytope?

pdf-format:
LIPIcs-STACS-2020-49.pdf (0.5 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI