No Cover Image

Conference Paper/Proceeding/Abstract 585 views 39 downloads

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

Julian D'Costa, Lefaucheux Engel, Eike Neumann, Joel Ouaknine, James Worrell

LIPIcs, MFCS 2022, Volume: 241

Swansea University Author: Eike Neumann

  • 61278.pdf

    PDF | Version of Record

    © Julian D’Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell; licensed under Creative Commons License CC-BY 4.0

    Download (703.69KB)

Check full text

DOI (Published version): 10.4230/LIPIcs.MFCS.2022.39

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 e...

Full description

Published in: LIPIcs, MFCS 2022
ISBN: 978-395977256-3
ISSN: 1868-8969
Published: Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern,Germany 2022
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa61278
Tags: Add Tag
No Tags, Be the first to tag this record!
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.
College: Faculty of Science and Engineering
Funders: Julian D’Costa: emmy.network foundation under the aegis of the Fondation de Luxembourg. Joël Ouaknine: Also affiliated with Keble College, Oxford as emmy.network Fellow, and supported by DFG grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science).

Similar Items