On the skolem problem for continuous linear dynamical systems
LIPIcs
Chonev, Ventsislav K
Ouaknine, Joël
Worrell, James
ddc:004
ddc:006
The Continuous Skolem Problem asks whether a real-valued function satisfying a linear differen-
tial 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 continuous-
time 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 de-
cidability 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.
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik
2016
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.app.ist.ac.at/record/1069
https://research-explorer.app.ist.ac.at/download/1069/5213
Chonev VK, Ouaknine J, Worrell J. On the skolem problem for continuous linear dynamical systems. In: Vol 55. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik; 2016. doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2016.100">10.4230/LIPIcs.ICALP.2016.100</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.ICALP.2016.100
info:eu-repo/grantAgreement/FWF//S 11407_N23
info:eu-repo/grantAgreement/EC/FP7/279307
info:eu-repo/grantAgreement/EC/FP7/267989
info:eu-repo/semantics/openAccess