On the skolem problem for continuous linear dynamical systemsReport as inadecuate




On the skolem problem 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 the skolem problem for continuous linear dynamical systems. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).Citable link to this page:

 

On the skolem problem for continuous linear dynamical systems

Abstract: The Continuous Skolem Problem asks whether a real-valued function satisfying a linear differential equation has a zero in a given interval of real numbers. This is a fundamental reachability problem for continuous linear dynamical systems, such as linear hybrid automata and continuoustime Markov chains. Decidability of the problem is currently open - indeed decidability is open even for the sub-problem in which a zero is sought in a bounded interval. In this paper we show decidability of the bounded problem subject to Schanuel's Conjecture, a unifying conjecture in transcendental number theory. We furthermore analyse the unbounded problem in terms of the frequencies of the differential equation, that is, the imaginary parts of the characteristic roots. We show that the unbounded problem can be reduced to the bounded problem if there is at most one rationally linearly independent frequency, or if there are two rationally linearly independent frequencies and all characteristic roots are simple. We complete the picture by showing that decidability of the unbounded problem in the case of two (or more) rationally linearly independent frequencies would entail a major new effectiveness result in Diophantine approximation, namely computability of the Diophantine-approximation types of all real algebraic numbers.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Publisher's versionDate of acceptance:2016-04-15Notes:© Ventsislav Chonev, Joël Ouaknine, and James Worrell; licensed under Creative Commons License CC-BY

Bibliographic Details

Publisher: Schloss Dagstuhl – Leibniz Center for Informatics

Publisher Website: http://www.dagstuhl.de/

Host: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)see more from them

Publication Website: http://www.easyconferences.eu/icalp2016/

Volume: 55

Issue Date: 2016-08Identifiers

Doi: https://doi.org/10.4230/LIPIcs.ICALP.2016.100

Issn: 1868-8969

Uuid: uuid:8df60f97-c14c-48ce-ba76-c736bd14ab38

Urn: uri:8df60f97-c14c-48ce-ba76-c736bd14ab38

Pubs-id: pubs:526192 Item Description

Type: conference-paper;

Version: Publisher's versionKeywords: differential equations reachability Baker’s Theorem Schanuel’s Conjecture semi-algebraic sets

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:8df60f97-c14c-48ce-ba76-c736bd14ab38



DOWNLOAD PDF




Related documents