<div class="csl-bib-body">
<div class="csl-entry">Kenison, G. J., Klurman, O., Lefaucheux, E., Luca, F., Moree, P., Ouaknine, J., Whiteland, M., & Worrell, J. (2021). On Positivity and Minimality for Second-Order Holonomic Sequences. In F. Bonchi & S. Puglisi (Eds.), <i>46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)</i> (pp. 1–15). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2021.67</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/19886
-
dc.description.abstract
An infinite sequence unn of real numbers is holonomic (also known as P-recursive or P-finite) if it satisfies a linear recurrence relation with polynomial coefficients. Such a sequence is said to be positive if each un ≥ 0, and minimal if, given any other linearly independent sequence vnn satisfying the same recurrence relation, the ratio un/vn → 0 as n → ∞. In this paper we give a Turing reduction of the problem of deciding positivity of second-order holonomic sequences to that of deciding minimality of such sequences. More specifically, we give a procedure for determining positivity of second-order holonomic sequences that terminates in all but an exceptional number of cases, and we show that in these exceptional cases positivity can be determined using an oracle for deciding minimality.
en
dc.description.sponsorship
WWTF Wiener Wissenschafts-, Forschu und Technologiefonds
-
dc.description.sponsorship
European Commission
-
dc.language.iso
en
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
holonomic sequences
en
dc.subject
minimal solutions
en
dc.subject
positivity problem
en
dc.title
On Positivity and Minimality for Second-Order Holonomic Sequences
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.contributor.affiliation
School of Mathematics, University of Bristol, UK
-
dc.contributor.affiliation
Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
-
dc.contributor.affiliation
School of Mathematics, University of the Witwatersrand, Johannesburg, South Africa
-
dc.contributor.affiliation
Max Planck Institute for Mathematics, Bonn, Germany
-
dc.contributor.affiliation
Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
-
dc.contributor.affiliation
Fonds De La Recherche Scientifique - FNRS
-
dc.contributor.affiliation
Department of Computer Science, University of Oxford, UK