No Cover Image

Conference Paper/Proceeding/Abstract 390 views 22 downloads

On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets

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

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Volume: 202, Pages: 33:1 - 33:21

Swansea University Author: Eike Neumann

  • 60143.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 (789.43KB)

Check full text

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

Abstract

We study the computational complexity of the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets, or equivalently the Termination Problem for affine loops with compact semialgebraic guard sets. Consider the fragment of the theory of the reals consisting of negat...

Full description

Published in: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
ISBN: 978-3-95977-201-3
ISSN: 1868-8969
Published: Dagstuhl, Germany Schloss Dagstuhl -- Leibniz-Zentrum für Informatik 2021
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa60143
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2022-06-07T12:52:07Z
last_indexed 2022-06-29T03:20:13Z
id cronfa60143
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2022-06-28T14:38:33.7921643</datestamp><bib-version>v2</bib-version><id>60143</id><entry>2022-06-07</entry><title>On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets</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-06-07</date><deptcode>SCS</deptcode><abstract>We study the computational complexity of the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets, or equivalently the Termination Problem for affine loops with compact semialgebraic guard sets. Consider the fragment of the theory of the reals consisting of negation-free &#x2203; &#x2200;-sentences without strict inequalities. We derive several equivalent characterisations of the associated complexity class which demonstrate its robustness and illustrate its expressive power. We show that the Compact Escape Problem is complete for this class.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)</journal><volume>202</volume><journalNumber/><paginationStart>33:1</paginationStart><paginationEnd>33:21</paginationEnd><publisher>Schloss Dagstuhl -- Leibniz-Zentrum f&#xFC;r Informatik</publisher><placeOfPublication>Dagstuhl, Germany</placeOfPublication><isbnPrint/><isbnElectronic>978-3-95977-201-3</isbnElectronic><issnPrint/><issnElectronic>1868-8969</issnElectronic><keywords>Discrete linear dynamical systems, Program termination, Compact semialgebraic sets, Theory of the reals</keywords><publishedDay>18</publishedDay><publishedMonth>8</publishedMonth><publishedYear>2021</publishedYear><publishedDate>2021-08-18</publishedDate><doi>10.4230/LIPIcs.MFCS.2021.33</doi><url>https://drops.dagstuhl.de/opus/volltexte/2021/14473</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: ERC grant AVS-ISS (648701), and DFG grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science). Jo&#xEB;l Ouaknine is also affiliated with Keble College, Oxford as emmy.network Fellow. James Worrell: EPSRC Fellowship EP/N008197/1.</funders><lastEdited>2022-06-28T14:38:33.7921643</lastEdited><Created>2022-06-07T13:48:08.0703891</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>Engel</firstname><surname>Lefaucheux</surname><order>1</order></author><author><firstname>Julian</firstname><surname>D'Costa</surname><order>2</order></author><author><firstname>Eike</firstname><surname>Neumann</surname><order>3</order></author><author><firstname>Jo&#xEB;l</firstname><surname>Ouaknine</surname><order>4</order></author><author><firstname>James</firstname><surname>Worrell</surname><order>5</order></author></authors><documents><document><filename>60143__24404__3818df778ef041928357345083f044af.pdf</filename><originalFilename>60143.pdf</originalFilename><uploaded>2022-06-28T14:27:21.7784836</uploaded><type>Output</type><contentLength>808377</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-06-28T14:38:33.7921643 v2 60143 2022-06-07 On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets 1bf535eaa8d6fcdfbd464a511c1c0c78 Eike Neumann Eike Neumann true false 2022-06-07 SCS We study the computational complexity of the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets, or equivalently the Termination Problem for affine loops with compact semialgebraic guard sets. Consider the fragment of the theory of the reals consisting of negation-free ∃ ∀-sentences without strict inequalities. We derive several equivalent characterisations of the associated complexity class which demonstrate its robustness and illustrate its expressive power. We show that the Compact Escape Problem is complete for this class. Conference Paper/Proceeding/Abstract 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) 202 33:1 33:21 Schloss Dagstuhl -- Leibniz-Zentrum für Informatik Dagstuhl, Germany 978-3-95977-201-3 1868-8969 Discrete linear dynamical systems, Program termination, Compact semialgebraic sets, Theory of the reals 18 8 2021 2021-08-18 10.4230/LIPIcs.MFCS.2021.33 https://drops.dagstuhl.de/opus/volltexte/2021/14473 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: ERC grant AVS-ISS (648701), and DFG grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science). Joël Ouaknine is also affiliated with Keble College, Oxford as emmy.network Fellow. James Worrell: EPSRC Fellowship EP/N008197/1. 2022-06-28T14:38:33.7921643 2022-06-07T13:48:08.0703891 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Engel Lefaucheux 1 Julian D'Costa 2 Eike Neumann 3 Joël Ouaknine 4 James Worrell 5 60143__24404__3818df778ef041928357345083f044af.pdf 60143.pdf 2022-06-28T14:27:21.7784836 Output 808377 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 On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
spellingShingle On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
Eike Neumann
title_short On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
title_full On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
title_fullStr On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
title_full_unstemmed On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
title_sort On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
author_id_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78
author_id_fullname_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78_***_Eike Neumann
author Eike Neumann
author2 Engel Lefaucheux
Julian D'Costa
Eike Neumann
Joël Ouaknine
James Worrell
format Conference Paper/Proceeding/Abstract
container_title 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
container_volume 202
container_start_page 33:1
publishDate 2021
institution Swansea University
isbn 978-3-95977-201-3
issn 1868-8969
doi_str_mv 10.4230/LIPIcs.MFCS.2021.33
publisher Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
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/2021/14473
document_store_str 1
active_str 0
description We study the computational complexity of the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets, or equivalently the Termination Problem for affine loops with compact semialgebraic guard sets. Consider the fragment of the theory of the reals consisting of negation-free ∃ ∀-sentences without strict inequalities. We derive several equivalent characterisations of the associated complexity class which demonstrate its robustness and illustrate its expressive power. We show that the Compact Escape Problem is complete for this class.
published_date 2021-08-18T04:18:00Z
_version_ 1763754199751852032
score 11.000841

Similar Items