No Cover Image

Conference Paper/Proceeding/Abstract 555 views 46 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!
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.
Keywords: Discrete linear dynamical systems, Program termination, Compact semialgebraic sets, Theory of the reals
College: Faculty of Science and Engineering
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.
Start Page: 33:1
End Page: 33:21

Similar Items