No Cover Image

Conference Paper/Proceeding/Abstract 389 views 17 downloads

Decision Problems for Second-Order Holonomic Recurrences

Eike Neumann, Joël Ouaknine, James Worrell

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Volume: 198, Pages: 99:1 - 99:20

Swansea University Author: Eike Neumann

  • 60144.pdf

    PDF | Version of Record

    © Eike Neumann, Joël Ouaknine, and James Worrell; licensed under Creative Commons License CC-BY 4.0

    Download (707.26KB)

Check full text

DOI (Published version): 10.4230/LIPIcs.ICALP.2021.99

Abstract

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...

Full description

Published in: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
ISBN: 978-3-95977-195-5
ISSN: 1868-8969
Published: Dagstuhl, Germany Schloss Dagstuhl -- Leibniz-Zentrum für Informatik 2021
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa60144
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: 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.
Keywords: Holonomic sequences, Positivity Problem, Skolem Problem
College: Faculty of Science and Engineering
Funders: Joël Ouaknine: ERC grant AVS-ISS (648701) and DFG grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science). James Worrell: EPSRC Fellowship EP/N008197/1.
Start Page: 99:1
End Page: 99:20

Similar Items