No Cover Image

Conference Paper/Proceeding/Abstract 415 views 25 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!
first_indexed 2022-09-20T07:31:35Z
last_indexed 2023-01-13T19:21:57Z
id cronfa61278
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2022-10-11T15:56:05.6005032</datestamp><bib-version>v2</bib-version><id>61278</id><entry>2022-09-20</entry><title>Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set</title><swanseaauthors><author><sid>1bf535eaa8d6fcdfbd464a511c1c0c78</sid><firstname>Eike</firstname><surname>Neumann</surname><name>Eike Neumann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2022-09-20</date><deptcode>SCS</deptcode><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.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>LIPIcs, MFCS 2022</journal><volume>241</volume><journalNumber/><paginationStart/><paginationEnd/><publisher>Schloss Dagstuhl &#x2013; Leibniz-Zentrum f&#xFC;r Informatik GmbH, Dagstuhl Publishing, Saarbr&#xFC;cken/Wadern,Germany</publisher><placeOfPublication/><isbnPrint>978-395977256-3</isbnPrint><isbnElectronic/><issnPrint>1868-8969</issnPrint><issnElectronic/><keywords/><publishedDay>2</publishedDay><publishedMonth>8</publishedMonth><publishedYear>2022</publishedYear><publishedDate>2022-08-02</publishedDate><doi>10.4230/LIPIcs.MFCS.2022.39</doi><url>https://drops.dagstuhl.de/opus/volltexte/2022/16797/</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders>Julian D&#x2019;Costa: emmy.network foundation under the aegis of the Fondation de Luxembourg. Jo&#xEB;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).</funders><projectreference/><lastEdited>2022-10-11T15:56:05.6005032</lastEdited><Created>2022-09-20T08:26:14.2131701</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Julian</firstname><surname>D'Costa</surname><order>1</order></author><author><firstname>Lefaucheux</firstname><surname>Engel</surname><order>2</order></author><author><firstname>Eike</firstname><surname>Neumann</surname><order>3</order></author><author><firstname>Joel</firstname><surname>Ouaknine</surname><order>4</order></author><author><firstname>James</firstname><surname>Worrell</surname><order>5</order></author></authors><documents><document><filename>61278__25156__fb3afc3fb7974ca7bbea53103fcaf98e.pdf</filename><originalFilename>61278.pdf</originalFilename><uploaded>2022-09-20T08:30:57.1930051</uploaded><type>Output</type><contentLength>720578</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>&#xA9; Julian D&#x2019;Costa, Engel Lefaucheux, Eike Neumann, Jo&#xEB;l Ouaknine, and James Worrell; licensed under Creative Commons License CC-BY 4.0</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling 2022-10-11T15:56:05.6005032 v2 61278 2022-09-20 Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set 1bf535eaa8d6fcdfbd464a511c1c0c78 Eike Neumann Eike Neumann true false 2022-09-20 SCS 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. Conference Paper/Proceeding/Abstract LIPIcs, MFCS 2022 241 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern,Germany 978-395977256-3 1868-8969 2 8 2022 2022-08-02 10.4230/LIPIcs.MFCS.2022.39 https://drops.dagstuhl.de/opus/volltexte/2022/16797/ COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 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). 2022-10-11T15:56:05.6005032 2022-09-20T08:26:14.2131701 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Julian D'Costa 1 Lefaucheux Engel 2 Eike Neumann 3 Joel Ouaknine 4 James Worrell 5 61278__25156__fb3afc3fb7974ca7bbea53103fcaf98e.pdf 61278.pdf 2022-09-20T08:30:57.1930051 Output 720578 application/pdf Version of Record true © Julian D’Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell; licensed under Creative Commons License CC-BY 4.0 true eng https://creativecommons.org/licenses/by/4.0/
title Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
spellingShingle Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
Eike Neumann
title_short Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
title_full Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
title_fullStr Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
title_full_unstemmed Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
title_sort Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
author_id_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78
author_id_fullname_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78_***_Eike Neumann
author Eike Neumann
author2 Julian D'Costa
Lefaucheux Engel
Eike Neumann
Joel Ouaknine
James Worrell
format Conference Paper/Proceeding/Abstract
container_title LIPIcs, MFCS 2022
container_volume 241
publishDate 2022
institution Swansea University
isbn 978-395977256-3
issn 1868-8969
doi_str_mv 10.4230/LIPIcs.MFCS.2022.39
publisher Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern,Germany
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url https://drops.dagstuhl.de/opus/volltexte/2022/16797/
document_store_str 1
active_str 0
description 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.
published_date 2022-08-02T04:20:00Z
_version_ 1763754325461434368
score 11.0133505

Similar Items