Conference Paper/Proceeding/Abstract 452 views 37 downloads
On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Volume: 202, Pages: 33:1 - 33:21
Swansea University Author: Eike Neumann
-
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)
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...
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" encoding="utf-8"?><rfc1807 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"><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><ORCID></ORCID><firstname>Eike</firstname><surname>Neumann</surname><name>Eike Neumann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2022-06-07</date><deptcode>MACS</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 ∃ ∀-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ü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>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders>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.</funders><projectreference/><lastEdited>2024-07-11T15:39:16.2701811</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><orcid></orcid><order>3</order></author><author><firstname>Joë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>© Julian D’Costa, Engel Lefaucheux, Eike Neumann, Joë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 |
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 MACS 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 Mathematics and Computer Science School COLLEGE CODE MACS 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. 2024-07-11T15:39:16.2701811 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-18T15:39:15Z |
_version_ |
1804293903800598528 |
score |
11.016235 |