Tags:Loop termination, Program verification and Skolem Problem
Abstract:
The Skolem Problem asks how to determine algorithmically whether a given linear recurrence sequence (such as the Fibonacci numbers) has a zero. It is a central question in dynamical systems and number theory, and has many connections to other branches of mathematics and computer science, such as program analysis and automated verification. Unfortunately, its decidability has been open for nearly a century! In this talk, I will present a brief survey of what is known on the Skolem Problem and related questions, including recent and ongoing developments.
Algorithms, Complexity, Verification: from Cook and Karp to Vardi; or, a Brief Glimpse of the Skolem Landscape