<div class="csl-bib-body">
<div class="csl-entry">Kenison, G., Nosan, K., Shirmohammadi, M., & Worrell, J. (2023). The Membership Problem for Hypergeometric Sequences with Quadratic Parameters. In A. Dickenstein, E. Tsigaridas, & G. Jeronimo (Eds.), <i>ISSAC ’23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation</i> (pp. 407–416). Association for Computing Machinery. https://doi.org/10.1145/3597066.3597121</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/188037
-
dc.description.abstract
Hypergeometric sequences are rational-valued sequences that satisfy first-order linear recurrence relations with polynomial coefficients; that is, a hypergeometric sequence is one that satisfies a recurrence of the form f(n)un = g(n)un − 1 where .
In this paper, we consider the Membership Problem for hypergeometric sequences: given a hypergeometric sequence and a target value , determine whether un = t for some index n. We establish decidability of the Membership Problem under the assumption that either (i) f and g have distinct splitting fields or (ii) f and g are monic polynomials that both split over a quadratic extension of . Our results are based on an analysis of the prime divisors of polynomial sequences and appearing in the recurrence relation.
-
dc.description.sponsorship
European Commission
-
dc.description.sponsorship
WWTF Wiener Wissenschafts-, Forschu und Technologiefonds
-
dc.language.iso
en
-
dc.subject
Membership Problem
en
dc.subject
Algebraic algorithms
en
dc.subject
Reachability
en
dc.title
The Membership Problem for Hypergeometric Sequences with Quadratic Parameters
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
Université Paris Cité, France
-
dc.contributor.affiliation
Université Paris Cité, France
-
dc.contributor.affiliation
University of Oxford, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.relation.isbn
9798400700392
-
dc.description.startpage
407
-
dc.description.endpage
416
-
dc.relation.grantno
ERC Consolidator Grant 2020
-
dc.relation.grantno
ICT19-018
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation
-
tuw.relation.publisher
Association for Computing Machinery
-
tuw.relation.publisherplace
New York
-
tuw.project.title
Automated Reasoning with Theories and Induction for Software Technologies
-
tuw.project.title
Distribution Recovery for Invariant Generation of Probabilistic Programs
-
tuw.researchTopic.id
C5
-
tuw.researchTopic.name
Computer Science Foundations
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-04 - Forschungsbereich Formal Methods in Systems Engineering
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
tuw.publisher.doi
10.1145/3597066.3597121
-
dc.description.numberOfPages
10
-
tuw.author.orcid
0000-0002-7661-7061
-
tuw.author.orcid
0000-0002-0998-5788
-
tuw.author.orcid
0000-0002-7779-2339
-
tuw.author.orcid
0000-0001-8151-2443
-
tuw.editor.orcid
0000-0003-4863-4953
-
tuw.editor.orcid
0009-0003-5015-3988
-
tuw.event.name
ISSAC 2023: International Symposium on Symbolic and Algebraic Computation 2023
en
tuw.event.startdate
24-07-2023
-
tuw.event.enddate
27-07-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Tromso
-
tuw.event.country
NO
-
tuw.event.presenter
Kenison, George
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.grantfulltext
none
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.openairetype
conference paper
-
item.cerifentitytype
Publications
-
item.fulltext
no Fulltext
-
item.languageiso639-1
en
-
crisitem.author.dept
E192-04 - Forschungsbereich Formal Methods in Systems Engineering
-
crisitem.author.dept
Universit� Paris Cit�
-
crisitem.author.dept
Universit� Paris Cit�
-
crisitem.author.dept
University of Oxford
-
crisitem.author.orcid
0000-0002-7661-7061
-
crisitem.author.orcid
0000-0002-0998-5788
-
crisitem.author.orcid
0000-0002-7779-2339
-
crisitem.author.orcid
0000-0001-8151-2443
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.project.funder
European Commission
-
crisitem.project.funder
WWTF Wiener Wissenschafts-, Forschu und Technologiefonds
