## On the Skolem Problem for continuous linear dynamical systems

*Ventsislav Chonev*,
*Joel
Ouaknine*, and *James Worrell*
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 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 give a reduction of the unbounded
problem to the bounded problem in the case of at most one rationally
linearly independent frequency or two rationally linearly independent
frequencies and simple characteristic roots. 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.

*Proceedings of ICALP 16*, LIPIcs ????, 2016. 19 pages.

PDF
© 2016 Ventsislav Chonev, Joel Ouaknine, and James Worrell.