---
_id: '1069'
abstract:
- lang: eng
  text: "The Continuous Skolem Problem asks whether a real-valued function satisfying
    a linear differen-\r\ntial equation has a zero in a given interval of real numbers.
    This is a fundamental reachability\r\nproblem for continuous linear dynamical
    systems, such as linear hybrid automata and continuous-\r\ntime Markov chains.
    Decidability of the problem is currently open – indeed decidability is open\r\neven
    for the sub-problem in which a zero is sought in a bounded interval. In this paper
    we show\r\ndecidability of the bounded problem subject to Schanuel’s Conjecture,
    a unifying conjecture in\r\ntranscendental number theory. We furthermore analyse
    the unbounded problem in terms of the\r\nfrequencies of the differential equation,
    that is, the imaginary parts of the characteristic roots.\r\nWe show that the
    unbounded problem can be reduced to the bounded problem if there is at most\r\none
    rationally linearly independent frequency, or if there are two rationally linearly
    independent\r\nfrequencies and all characteristic roots are simple. We complete
    the picture by showing that de-\r\ncidability of the unbounded problem in the
    case of two (or more) rationally linearly independent\r\nfrequencies would entail
    a major new effectiveness result in Diophantine approximation, namely\r\ncomputability
    of the Diophantine-approximation types of all real algebraic numbers."
acknowledgement: 'Ventsislav Chonev is supported by Austrian Science Fund (FWF) NFN
  Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant (279307:  Graph Games), and ERC
  Advanced Grant (267989: QUAREM).'
alternative_title:
- LIPIcs
article_number: '100'
article_processing_charge: No
author:
- first_name: Ventsislav K
  full_name: Chonev, Ventsislav K
  id: 36CBE2E6-F248-11E8-B48F-1D18A9856A87
  last_name: Chonev
- first_name: Joël
  full_name: Ouaknine, Joël
  last_name: Ouaknine
- first_name: James
  full_name: Worrell, James
  last_name: Worrell
citation:
  ama: 'Chonev VK, Ouaknine J, Worrell J. On the skolem problem for continuous linear
    dynamical systems. In: Vol 55. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2016. doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2016.100">10.4230/LIPIcs.ICALP.2016.100</a>'
  apa: 'Chonev, V. K., Ouaknine, J., &#38; Worrell, J. (2016). On the skolem problem
    for continuous linear dynamical systems (Vol. 55). Presented at the ICALP: Automata,
    Languages and Programming, Rome, Italy: Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2016.100">https://doi.org/10.4230/LIPIcs.ICALP.2016.100</a>'
  chicago: Chonev, Ventsislav K, Joël Ouaknine, and James Worrell. “On the Skolem
    Problem for Continuous Linear Dynamical Systems,” Vol. 55. Schloss Dagstuhl -
    Leibniz-Zentrum für Informatik, 2016. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2016.100">https://doi.org/10.4230/LIPIcs.ICALP.2016.100</a>.
  ieee: 'V. K. Chonev, J. Ouaknine, and J. Worrell, “On the skolem problem for continuous
    linear dynamical systems,” presented at the ICALP: Automata, Languages and Programming,
    Rome, Italy, 2016, vol. 55.'
  ista: 'Chonev VK, Ouaknine J, Worrell J. 2016. On the skolem problem for continuous
    linear dynamical systems. ICALP: Automata, Languages and Programming, LIPIcs,
    vol. 55, 100.'
  mla: Chonev, Ventsislav K., et al. <i>On the Skolem Problem for Continuous Linear
    Dynamical Systems</i>. Vol. 55, 100, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2016, doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2016.100">10.4230/LIPIcs.ICALP.2016.100</a>.
  short: V.K. Chonev, J. Ouaknine, J. Worrell, in:, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2016.
conference:
  end_date: 2016-07-15
  location: Rome, Italy
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 2016-07-12
date_created: 2018-12-11T11:49:59Z
date_published: 2016-08-01T00:00:00Z
date_updated: 2025-06-03T11:32:08Z
day: '01'
ddc:
- '004'
- '006'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.ICALP.2016.100
ec_funded: 1
file:
- access_level: open_access
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:16:26Z
  date_updated: 2018-12-12T10:16:26Z
  file_id: '5213'
  file_name: IST-2017-778-v1+1_LIPIcs-ICALP-2016-100.pdf
  file_size: 521415
  relation: main_file
file_date_updated: 2018-12-12T10:16:26Z
fulldoi: https://doi.org/10.4230/LIPIcs.ICALP.2016.100
has_accepted_license: '1'
intvolume: '        55'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '267989'
  name: Quantitative Reactive Modeling
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6314'
pubrep_id: '778'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the skolem problem for continuous linear dynamical systems
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 55
year: '2016'
...