License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.39
URN: urn:nbn:de:0030-drops-168374
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16837/
Go to the corresponding LIPIcs Volume Portal

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

Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set

pdf-format:
LIPIcs-MFCS-2022-39.pdf (0.7 MB)

Abstract

We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for every orbit of a rational matrix to escape a compact semialgebraic set defined over rational data. Our bound is doubly exponential in the ambient dimension, singly exponential in the degrees of the polynomials used to define the semialgebraic set, and singly exponential in the bitsize of the coefficients of these polynomials and the bitsize of the matrix entries. We show that our bound is tight by providing a matching lower bound.

BibTeX - Entry

@InProceedings{dcosta_et_al:LIPIcs.MFCS.2022.39,
  author =	{D'Costa, Julian and Lefaucheux, Engel and Neumann, Eike and Ouaknine, Jo\"{e}l and Worrell, James},
  title =	{{Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16837},
  URN =		{urn:nbn:de:0030-drops-168374},
  doi =		{10.4230/LIPIcs.MFCS.2022.39},
  annote =	{Keywords: Discrete linear dynamical systems, Program termination, Compact semialgebraic sets, Uniform termination bounds}
}

Keywords: Discrete linear dynamical systems, Program termination, Compact semialgebraic sets, Uniform termination bounds
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

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