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
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 Distribution Recovery for Invariant Generation of Probabilistic Programs
-
Project ID:
ERC Consolidator Grant 2020 ICT19-018
-
Funder:
European Commission WWTF Wiener Wissenschafts-, Forschu und Technologiefonds
