Record link: 
http://hdl.handle.net/20.500.12708/188037
-
Title: 
The Membership Problem for Hypergeometric Sequences with Quadratic Parameters
en
Citation: 
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.), ISSAC ’23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (pp. 407–416). Association for Computing Machinery. https://doi.org/10.1145/3597066.3597121
-
Publisher DOI: 
10.1145/3597066.3597121
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Kenison, George 
Nosan, Klara 
Shirmohammadi, Mahsa 
Worrell, James 
-
Organisational Unit: 
E192-04 - Forschungsbereich Formal Methods in Systems Engineering 
E192 - Institut für Logic and Computation 
-
Published in: 
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation 
-
ISBN: 
9798400700392
-
Date (published): 
24-Jul-2023
-
Event name: 
ISSAC 2023: International Symposium on Symbolic and Algebraic Computation 2023 
en
Event date: 
24-Jul-2023 - 27-Jul-2023
-
Event place: 
Tromso, Norway
-
Number of Pages: 
10
-
Publisher: 
Association for Computing Machinery, New York
-
Keywords: 
Membership Problem; Algebraic algorithms; Reachability
en
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.
-
Project title: 
Automated Reasoning with Theories and Induction for Software Technologies: ERC Consolidator Grant 2020 (European Commission) 
Distribution Recovery for Invariant Generation of Probabilistic Programs: ICT19-018 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds) 
-
Research Areas: 
Computer Science Foundations: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

359
checked on Nov 21, 2023

Google ScholarTM

Check