Abstract
It is well understood that the interaction between discrete and continuous dynamics makes hybrid automata difficult to analyse algorithmically. However it is already the case that many natural verification questions concerning only the continuous dynamics of such systems are extremely challenging. This remains so even for linear dynamical systems, such as linear hybrid automata and continuoustime Markov chains, whose evolution is detemined by linear differential equations. For example, one can ask to decide whether it is possible to escape a particular location of a linear hybrid automaton, given initial values of the continuous variables. Likewise one can ask whether a given set of probability distributions is reachable during the evolution of continuoustime Markov chain.
This talk focusses on reachability problems for solutions of linear differential equations. A central decision problem in this area is the Continuous Skolem Problem, which asks whether a realvalued function satisfying an ordinary linear differential equation has a zero. This can be seen as a continuous analog of the Skolem Problem for linear recurrence sequences, which asks whether the sequence satisfying a given recurrence has a zero term. For both the discrete and continuous versions of the Skolem Problem, decidability is open.
We show that the Continuous Skolem Problem lies at the heart of many natural verification questions on linear dynamical systems. We describe some recent work, done in collaboration with Chonev and Ouaknine, that uses results in transcendence theory and real algebraic geometry to obtain decidability for certain variants of the problem. In particular, we consider a bounded version of the Continuous Skolem Problem, corresponding to timebounded reachability. We prove decidability of the bounded problem assuming Schanuel's conjecture, one of the main conjectures in transcendence theory. We describe some partial decidability results in the unbounded case and discuss mathematical obstacles to proving decidability of the Continuous Skolem Problem in full generality.
BibTeX  Entry
@InProceedings{worrell:LIPIcs:2015:5396,
author = {James Worrell},
title = {{Reachability Problems for Continuous Linear Dynamical Systems (Invited Paper)}},
booktitle = {26th International Conference on Concurrency Theory (CONCUR 2015)},
pages = {1717},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897910},
ISSN = {18688969},
year = {2015},
volume = {42},
editor = {Luca Aceto and David de Frutos Escrig},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5396},
URN = {urn:nbn:de:0030drops53960},
doi = {10.4230/LIPIcs.CONCUR.2015.17},
annote = {Keywords: Linear differential Equations, Hybrid Automata, Schanuel's Conjecture}
}
Keywords: 

Linear differential Equations, Hybrid Automata, Schanuel's Conjecture 
Collection: 

26th International Conference on Concurrency Theory (CONCUR 2015) 
Issue Date: 

2015 
Date of publication: 

26.08.2015 