Thursday, September 10, 2015
Speaker: Joel Ouaknine
Venue: IST Austria
Room: Mondi 1
I will discuss the Continuous Skolem Problem, a reachability problem for linear dynamical systems whose decidability is open, and which lies at the heart of many natural verification questions for cyber-physical systems (modelled as hybrid automata) and continuous-time Markov chains. This problem is also equivalent to deciding the existence of zeros for single-variable, linear ordinary differential equations with rational (or algebraic) coefficients.
I will describe some recent work (joint with Ventsi Chonev and James Worrell) using results in transcendence theory, Diophantine geometry, real algebraic geometry, and model theory to obtain decidability for certain variants of the problem, partially answering open questions (among others) of Bell, Delvenne, Jungers, and Blondel. In particular, we consider a bounded version of the Continuous Skolem Problem (corresponding to time-bounded reachability), and show decidability of the bounded problem assuming Schanuel’s Conjecture, a central and unifying conjecture in transcendence theory. I will also describe some partial decidability results in the unbounded case and discuss mathematical obstacles to proving decidability of the Continuous Skolem Problem in full generality.