Conference Paper/Proceeding/Abstract 557 views 42 downloads
Decision Problems for Second-Order Holonomic Recurrences
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Volume: 198, Pages: 99:1 - 99:20
Swansea University Author: Eike Neumann
-
PDF | Version of Record
© Eike Neumann, Joël Ouaknine, and James Worrell; licensed under Creative Commons License CC-BY 4.0
Download (707.26KB)
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...
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 |