License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2015.5
URN: urn:nbn:de:0030-drops-56410
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5641/
Go to the corresponding LIPIcs Volume Portal

Worrell, James

Reachability Problems for Continuous Linear Dynamical Systems (Invited Talk)

pdf-format:
25.pdf (0.3 MB)

Abstract

This talk is about reachability problems for continuous-time linear
dynamical systems. A central decision problem in the area is the
Continuous Skolem Problem. In particular, this problem lies at the heart of several reachability questions in continuous-time Markov chains and linear hybrid automata.

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 time-bounded reachability. We prove decidability of the bounded problem assuming Schanuel's conjecture, a central conjecture in transcendence theory. We also describe some partial decidability results in the unbounded case in the case of functions satisfying differential equations of fixed low order.

Finally, we give evidence of significant mathematical obstacles to
proving decidability of the Continuous Skolem Problem in full
generality by exhibiting some number-theoretic consequences of the
existence of a decision procedure for this problem.

BibTeX - Entry

@InProceedings{worrell:LIPIcs:2015:5641,
  author =	{James Worrell},
  title =	{{Reachability Problems for Continuous Linear Dynamical Systems (Invited Talk)}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{5--6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Prahladh Harsha and G. Ramalingam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5641},
  URN =		{urn:nbn:de:0030-drops-56410},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.5},
  annote =	{Keywords: Linear Differential Equations, Continuous-Time Markov Chains, Hybrid Automata, Schanuel's Conjecture}
}

Keywords: Linear Differential Equations, Continuous-Time Markov Chains, Hybrid Automata, Schanuel's Conjecture
Collection: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Issue Date: 2015
Date of publication: 14.12.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI