Decision problems for linear recurrence sequences

Joël Ouaknine and James Worrell

Linear recurrence sequences permeate a vast number of areas of mathematics and computer science. In this paper, we survey the state of the art concerning certain fundamental decision problems for linear recurrence sequences, namely the Skolem Problem (does the sequence have a zero?), the Positivity Problem (is the sequence always positive?), and the Ultimate Positivity Problem (is the sequence ultimately always positive?).

Proceedings of RP 12 (invited paper), LNCS 7550, 2012. 8 pages.

PDF © 2012 Springer-Verlag.

Imprint / Data Protection