On recurrent reachability for continuous linear dynamical systemsReport as inadecuate




On recurrent reachability for continuous linear dynamical systems - Download this document for free, or read online. Document in PDF available to download.

Reference: Chonev, V, Ouaknine, J and Worrell, J et al., (2016). On recurrent reachability for continuous linear dynamical systems. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016).Citable link to this page:

 

On recurrent reachability for continuous linear dynamical systems

Abstract: The continuous evolution of a wide variety of systems, including continuous-time Markov chains and linear hybrid automata, can be described in terms of linear differential equations. In this paper we study the decision problem of whether the solution x(t) of a system of linear differential equations dx/dt = Ax reaches a target halfspace infinitely often. This recurrent reachability problem can equivalently be formulated as the following Infinite Zeros Problem: does a real-valued function f: R0 → R satisfying a given linear differential equation have infinitely many zeros? Our main decidability result is that if the differential equation has order at most 7, then the Infinite Zeros Problem is decidable. On the other hand, we show that a decision procedure for the Infinite Zeros Problem at order 9 (and above) would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Accepted manuscriptDate of acceptance:2016-04-04 Funder: Austrian Science Fund   Funder: European Research Council   Funder: Engineering and Physical Sciences Research Council   Notes:Copyright © held by owner/author(s). Publication rights licensed to ACM.

Bibliographic Details

Publisher: Association for Computing Machinery

Publisher Website: http://www.acm.org/

Journal: 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016)see more from them

Publication Website: http://lics.siglog.org/lics16/

Volume: 05-08-July-2016

Extent: 515-524

Issue Date: 2016-07Identifiers

Doi: https://doi.org/10.1145/2933575.2934548

Issn: 1043-6871

Uuid: uuid:da71face-32f6-4e5c-a132-820497bab752

Urn: uri:da71face-32f6-4e5c-a132-820497bab752

Pubs-id: pubs:532121 Item Description

Type: conference-paper;

Version: Accepted manuscriptKeywords: linear dynamical systems reachability, differential equations Diophantine Approximation Skolem problem

Relationships





Author: Chonev, V - - - Ouaknine, J - Oxford, MPLS, Computer Science St Johns College - - - Worrell, J - Oxford, MPLS, Computer Science G

Source: https://ora.ox.ac.uk/objects/uuid:da71face-32f6-4e5c-a132-820497bab752



DOWNLOAD PDF




Related documents