On the Decidability of the Bounded Continuous Skolem Problem.
Ventsislav Chonev, Joël Ouaknine, James Worrell · arXiv (Cornell University) · 2015
The Continuous Skolem Problem asks whether a real-valued function satisfying an ordinary linear differential equation has a zero in a given interval of real numbers. This is a fundamental reachability problem arising in the analysis of continuous linear dynamical systems, including linear hybrid automata and continuous-time Markov chains. Not only is decidability of this problem open, but 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 central conjecture in transcendental number theory. Regarding the unbounded case, by way of hardness we show that decidability of the Continuous Skolem Problem would entail a major new effectiveness result in Diophantine approximation, namely computability of the Diophantine-approximation types of all real algebraic numbers.