License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.130
URN: urn:nbn:de:0030-drops-181821
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18182/
Go to the corresponding LIPIcs Volume Portal

Kenison, George ; Nieuwveld, Joris ; Ouaknine, Joël ; Worrell, James

Positivity Problems for Reversible Linear Recurrence Sequences

pdf-format:
LIPIcs-ICALP-2023-130.pdf (0.7 MB)

Abstract

It is a longstanding open problem whether there is an algorithm to decide the Positivity Problem for linear recurrence sequences (LRS) over the integers, namely whether given such a sequence, all its terms are non-negative. Decidability is known for LRS of order 5 or less, i.e., for those sequences in which every new term depends linearly on the previous five (or fewer) terms. For simple LRS (i.e., those sequences whose characteristic polynomials have no repeated roots), decidability of Positivity is known up to order 9.
In this paper, we focus on the important subclass of reversible LRS, i.e., those integer LRS ⟨u_n⟩_{n=0}^∞ whose bi-infinite completion ⟨u_n⟩_{n=-∞}^∞ also takes exclusively integer values; a typical example is the classical Fibonacci (bi-)sequence ⟨ … , 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, … ⟩. Our main results are that Positivity is decidable for reversible LRS of order 11 or less, and for simple reversible LRS of order 17 or less.

BibTeX - Entry

@InProceedings{kenison_et_al:LIPIcs.ICALP.2023.130,
  author =	{Kenison, George and Nieuwveld, Joris and Ouaknine, Jo\"{e}l and Worrell, James},
  title =	{{Positivity Problems for Reversible Linear Recurrence Sequences}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{130:1--130:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18182},
  URN =		{urn:nbn:de:0030-drops-181821},
  doi =		{10.4230/LIPIcs.ICALP.2023.130},
  annote =	{Keywords: The Positivity Problem, Linear Recurrence Sequences, Verification}
}

Keywords: The Positivity Problem, Linear Recurrence Sequences, Verification
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

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