BeDeJuBl_2.pdf (416.31 kB)
The continuous Skolem-Pisot problem
journal contribution
posted on 2013-04-04, 15:04 authored by Paul Bell, Jean-Charles Delvenne, Raphael M. Jungers, Vincent BlondelWe study decidability and complexity questions related to a continu-
ous analogue of the Skolem-Pisot problem concerning the zeros and non-
negativity of a linear recurrent sequence. In particular, we show that the
continuous version of the nonnegativity problem is NP-hard in general and
we show that the presence of a zero is decidable for several subcases, in-
cluding instances of depth two or less, although the decidability in general
is left open. The problems may also be stated as reachability problems
related to real zeros of exponential polynomials or solutions to initial value
problems of linear dfferential equations, which are interesting problems
in their own right.
History
School
- Science
Department
- Computer Science
Citation
BELL, P.C. ... et al, 2010. The continuous Skolem-Pisot problem. Theoretical Computer Science, 411 (40-42), pp.3625-3634.Publisher
© ElsevierVersion
- AM (Accepted Manuscript)
Publication date
2010Notes
This is the author’s version of a work that was accepted for publication in the journal Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published at: http://dx.doi.org/10.1016/j.tcs.2010.06.005ISSN
0304-3975Publisher version
Language
- en