No Cover Image

Conference Paper/Proceeding/Abstract 452 views 35 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!
first_indexed 2022-06-07T12:59:34Z
last_indexed 2023-01-11T14:41:55Z
id cronfa60144
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2022-10-31T14:36:04.6380468</datestamp><bib-version>v2</bib-version><id>60144</id><entry>2022-06-07</entry><title>Decision Problems for Second-Order Holonomic Recurrences</title><swanseaauthors><author><sid>1bf535eaa8d6fcdfbd464a511c1c0c78</sid><firstname>Eike</firstname><surname>Neumann</surname><name>Eike Neumann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2022-06-07</date><deptcode>SCS</deptcode><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.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)</journal><volume>198</volume><journalNumber/><paginationStart>99:1</paginationStart><paginationEnd>99:20</paginationEnd><publisher>Schloss Dagstuhl -- Leibniz-Zentrum f&#xFC;r Informatik</publisher><placeOfPublication>Dagstuhl, Germany</placeOfPublication><isbnPrint/><isbnElectronic>978-3-95977-195-5</isbnElectronic><issnPrint/><issnElectronic>1868-8969</issnElectronic><keywords>Holonomic sequences, Positivity Problem, Skolem Problem</keywords><publishedDay>2</publishedDay><publishedMonth>7</publishedMonth><publishedYear>2021</publishedYear><publishedDate>2021-07-02</publishedDate><doi>10.4230/LIPIcs.ICALP.2021.99</doi><url>https://drops.dagstuhl.de/opus/volltexte/2021/14168</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders>Jo&#xEB;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.</funders><projectreference/><lastEdited>2022-10-31T14:36:04.6380468</lastEdited><Created>2022-06-07T13:55:57.3081475</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Eike</firstname><surname>Neumann</surname><order>1</order></author><author><firstname>Jo&#xEB;l</firstname><surname>Ouaknine</surname><order>2</order></author><author><firstname>James</firstname><surname>Worrell</surname><order>3</order></author></authors><documents><document><filename>60144__24403__b06968a1f54147b9a5637b811d2bfa48.pdf</filename><originalFilename>60144.pdf</originalFilename><uploaded>2022-06-28T14:22:39.2947868</uploaded><type>Output</type><contentLength>724232</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>&#xA9; Eike Neumann, Jo&#xEB;l Ouaknine, and James Worrell; licensed under Creative Commons License CC-BY 4.0</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling 2022-10-31T14:36:04.6380468 v2 60144 2022-06-07 Decision Problems for Second-Order Holonomic Recurrences 1bf535eaa8d6fcdfbd464a511c1c0c78 Eike Neumann Eike Neumann true false 2022-06-07 SCS 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. Conference Paper/Proceeding/Abstract 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 198 99:1 99:20 Schloss Dagstuhl -- Leibniz-Zentrum für Informatik Dagstuhl, Germany 978-3-95977-195-5 1868-8969 Holonomic sequences, Positivity Problem, Skolem Problem 2 7 2021 2021-07-02 10.4230/LIPIcs.ICALP.2021.99 https://drops.dagstuhl.de/opus/volltexte/2021/14168 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 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. 2022-10-31T14:36:04.6380468 2022-06-07T13:55:57.3081475 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Eike Neumann 1 Joël Ouaknine 2 James Worrell 3 60144__24403__b06968a1f54147b9a5637b811d2bfa48.pdf 60144.pdf 2022-06-28T14:22:39.2947868 Output 724232 application/pdf Version of Record true © Eike Neumann, Joël Ouaknine, and James Worrell; licensed under Creative Commons License CC-BY 4.0 true eng https://creativecommons.org/licenses/by/4.0/
title Decision Problems for Second-Order Holonomic Recurrences
spellingShingle Decision Problems for Second-Order Holonomic Recurrences
Eike Neumann
title_short Decision Problems for Second-Order Holonomic Recurrences
title_full Decision Problems for Second-Order Holonomic Recurrences
title_fullStr Decision Problems for Second-Order Holonomic Recurrences
title_full_unstemmed Decision Problems for Second-Order Holonomic Recurrences
title_sort Decision Problems for Second-Order Holonomic Recurrences
author_id_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78
author_id_fullname_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78_***_Eike Neumann
author Eike Neumann
author2 Eike Neumann
Joël Ouaknine
James Worrell
format Conference Paper/Proceeding/Abstract
container_title 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
container_volume 198
container_start_page 99:1
publishDate 2021
institution Swansea University
isbn 978-3-95977-195-5
issn 1868-8969
doi_str_mv 10.4230/LIPIcs.ICALP.2021.99
publisher Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url https://drops.dagstuhl.de/opus/volltexte/2021/14168
document_store_str 1
active_str 0
description 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.
published_date 2021-07-02T04:18:00Z
_version_ 1763754199872438272
score 11.013619

Similar Items