Author(s):

Chonev, Ventsislav; Ouaknine, Joël; Worrell, James

Title: 
On the skolem problem for continuous linear dynamical systems

Title Series: 
LIPIcs

Affiliation 
IST Austria 
Abstract: 
The Continuous Skolem Problem asks whether a realvalued 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 subproblem 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 Diophantineapproximation types of all real algebraic numbers.

Keywords: 
reachability; Differential equations; Baker’s theorem; Schanuel’s conjecture; semialgebraic sets

Conference Title:

ICALP: Automata, Languages and Programming

Volume: 
55

Conference Dates:

July 1115, 2016

Conference Location:

Rome, IT

Publisher:

Springer

Date Published:

20160101

Start Page: 
Article Number: 100

Copyright Statement: 
CC BY

Sponsor: 
Ventsislav Chonev is supported by Austrian Science Fund (FWF) NFN Grant No S11407N23 (RiSE/SHiNE), ERC Start grant (279307: Graph Games), and ERC Advanced Grant (267989: QUAREM).

URL: 

DOI: 
10.4230/LIPIcs.ICALP.2016.100

Open access: 
yes (OA journal) 