2026-07-24T17:45:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14168 2024-03-06T10:53:39Z ddc:004 open_access

Decision Problems for Second-Order Holonomic Recurrences Neumann, Eike Ouaknine, Joël Worrell, James holonomic sequences Positivity Problem Skolem Problem We study decision problems for sequences which obey a second-order holonomic recurrence of the form f(n + 2) = P(n) f(n + 1) + Q(n) f(n) with rational polynomial coefficients, where P is non-constant, Q is non-zero, and the degree of Q is smaller than or equal to that of P. We show that existence of infinitely many zeroes is decidable. We give partial algorithms for deciding the existence of a zero, positivity of all sequence terms, and positivity of all but finitely many sequence terms. If Q does not have a positive integer zero then our algorithms halt on almost all initial values (f(1), f(2)) for the recurrence. We identify a class of recurrences for which our algorithms halt for all initial values. We further identify a class of recurrences for which our algorithms can be extended to total ones. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eike Neumann and Joël Ouaknine and James Worrell 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.99 urn:nbn:de:0030-drops-141682 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.99 eng https://creativecommons.org/licenses/by/4.0/legalcode