Record link: 
http://hdl.handle.net/20.500.12708/101800
-
Title: 
On the Skolem Problem for Reversible Sequences
en
Citation: 
Kenison, G. (2022). On the Skolem Problem for Reversible Sequences. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) (pp. 61:1-61:15). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2022.61
-
Publisher DOI: 
10.4230/LIPIcs.MFCS.2022.61
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Kenison, George 
-
Organisational Unit: 
E192-04 - Forschungsbereich Formal Methods in Systems Engineering 
-
Published in: 
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) 
-
ISBN: 
978-3-95977-256-3
-
Volume: 
241
-
Date (published): 
22-Aug-2022
-
Event name: 
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) 
en
Event date: 
22-Aug-2022 - 26-Aug-2022
-
Event place: 
Vienna, Austria
-
Number of Pages: 
15
-
Publisher: 
Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
-
Keywords: 
Linear Recurrences; The Skolem Problem; Verification
-
Abstract: 
Given an integer linear recurrence sequence (Xn)∞ n=0, the Skolem Problem asks to determine whether there is an n ϵ N0 such that Xn = 0. Recent work by Lipton, Luca, Nieuwveld, Ouaknine, Purser, and Worrell proved that the Skolem Problem is decidable for a class of reversible sequences of order at most seven. Here we give an alternative proof of their result. Our novel approach employs a powerful result for Galois conjugates that lie on two concentric circles due to Dubickas and Smyth.
en
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: 
Mathematical and Algorithmic Foundations: 100%
-
Science Branch: 
1020 - Informatik: 100%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

100
checked on Nov 23, 2023

Google ScholarTM

Check