Conference item icon

Conference item

Universal skolem sets

Abstract:
It is a longstanding open problem whether there is an algorithm to decide the Skolem Problem for linear recurrence sequences, namely whether a given such sequence has a zero term. In this paper we introduce the notion of a Universal Skolem Set: an infinite subset S of the positive integers such that there is an effective procedure that inputs a linear recurrence sequence u = (u(n)) n ≥ 0 and decides whether u(n) = 0 for some n∈S. The main technical contribution of the paper is to exhibit such a set.
Publication status:
Published
Peer review status:
Peer reviewed

Actions

  • Cite

  • Print

Access Document

Files:
Publisher copy:
10.1109/LICS52264.2021.9470513

Authors

More by this author
Institution:
University of Oxford
Department:
COMPUTER SCIENCE
Sub department:
Computer Science
Role:
Author

More from this funder
Funder identifier:
http://dx.doi.org/10.13039/501100000266
Grant:
EP/N008197/1

Publisher:
IEEE
Host title:
Proceedings of the ACM/IEEE Symposium on Logic in Computer Science
Pages:
1-6
Publication date:
2021-07-07
Acceptance date:
2021-04-29
Event title:
36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021)
Event location:
Rome, Italy
Event website:
https://dl.acm.org/conference/lics
Event start date:
2021-06-29
Event end date:
2021-07-02
DOI:
EISBN:
978-1-6654-4895-6
ISBN:
978-1-6654-4896-3

Language:
English
Keywords:
Pubs id:
1177337
Local pid:
pubs:1177337
Deposit date:
2021-05-20
ARK identifier:

Terms of use

Views and Downloads





If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP