Topic#
Recursively defined sequences are foundational objects of study in the computational sciences; they arise naturally in areas such as: the analysis of algorithms, weighted automata, loop termination, and probabilistic models.
Aim#
The aim of WORReLL'23 is to bring together researchers from the community and showcase cutting-edge research. The one-day workshop will also celebrate the research contributions of Professor James Worrell (also known as Ben). For context, Ben is giving an invited talk at ICALP this year.
Coincidentally, the workshop is a few days prior to Ben’s birthday. We plan to celebrate with a birthday dinner on Sunday 09th July (the evening before the workshop), so please take this into consideration for planning your travel to Paderborn.
Participation#
To participate in-person, please register for WORReLL'23 through ICALP’s registration portal. To participate remotely over Zoom, please contact the organisers for further details.
#ICALP2023 #Workshops | July 10th
— ICALP 2023 (@ICALPconf) March 24, 2023
Workshop On Reachability, Recurrences, and Loops '23 (WORReLL'23)
👉Organizers:
> George Kenison @tu_wien
> Mahsa Shirmohammadi @IRIF_Paris @univ_paris_cite @INS2I_CNRS pic.twitter.com/tUhXQccIYu
Speakers, Talks, and Slides#
(Click on a talk title for the abstract and slides.)
On the Complexity of the Sum of Square Roots Problem — Nikhil Balaji (IIT Delhi)
Abstract: Given positive integers $a_1, \dots, a_n$ and $b_1, \dots, b_m$, the Sum of Square Roots (SSR) problem checks if $\sum \sqrt{a_i} > \sum \sqrt{b_j}$. While foundational in Computational Geometry, its complexity is in the Counting Hierarchy, and no simple lower bounds exist. This talk introduces a variant of SSR and presents non-uniform algorithms for it.
From Quantum Automata to Quaternions and Rational Pairing Functions — Paul Bell (Keele)
Abstract: We investigate the undecidability of the injectivity problem for Quantum Finite Automata (QFA), focusing on unique acceptance probability for input words. Using linear algebra and quaternions, we discuss state requirements for undecidability based on real or rational initial states.
Recursive Sequences and Numeration — Valérie Berthé (CNRS, Paris)
Abstract: This lecture explores linear recurrences through the lens of numeration systems and associated dynamical systems, focusing on the finiteness property (where elements with finite expansion form a ring) and its applications in fractal geometry and number theory.
Globe-Hopping — Dmitry Chistikov (Warwick)
Twisted Rational Zeros of Linearly Recurrent Sequences — Florian Luca (Witwatersrand)
Abstract: We examine the Tribonacci sequence’s 2-adic valuations, finding that Marques and Lengyel’s conjecture fails for most primes. We prove finiteness of “twisted rational zeros” in non-degenerate linear recurrences, extending the Skolem–Mahler–Lech theorem. Joint work with Bilu, Nieuwveld, Ouaknine, and Worrell.
Universal Skolem Sets — Joël Ouaknine (MPI-SWS)
Abstract: The Skolem Problem determines if a linear recurrence has a zero term. We review a new approach using Universal Skolem Sets—sets of integers for which this problem is decidable—based on joint work with Luca, Maynard, Noubissie, and Worrell.
The Positivity Problem for Recurrent Sequences — Veronika Pillwein (JKU)
Reachability Problems on Matrices and Maps — Igor Potapov (Liverpool)
The Membership Problem for Hypergeometric Sequences — Mahsa Shirmohammadi (CNRS, Paris)
Abstract: This talk is on the Membership problem for rational-valued hypergeometric sequences. Such sequences $\\langle u_n \\rangle_{n=0}^{\infty}$ satisfies a first-order linear recurrence relation with polynomial coefficients; that is, a recurrence of the form $f(n)u_n = g(n)u_{n-1}$ where $f,g \in \mathbb{Z}[x]$. The Membership Problem asks, given a hypergeometric sequence $\\langle u_n \\rangle_{n=0}^{\infty}$ and a target value $t\in \mathbb{Q}$, determine whether $t$ occurs in the sequence. We give hints on recent decidability results of the Membership Problem under the assumption that either (i) $f$ and $g$ have distinct splitting fields, (ii) $f$ and $g$ split totally over $\mathbb{Q}$, and (iii) $f$ and $g$ are monic polynomials that both split over a quadratic extension of $\mathbb{Q}$.
This talk is based on two papers appearing in ISSAC'22 and ISSAC'23, and are in collaboration with George Kenison, Amaury Pouly, Klara Nosan, and James Worrell.
Schedule#
(All times are UTC+02:00)
08:00–09:00 Registration
09:00–09:45 Valérie Berthé
09:45–10:30 Dmitry Chistikov
Coffee Break
11:00–11:45 Mahsa Shirmohammadi
11:45–12:30 Florian Luca
Lunch
14:05–14:25 Veronika Pillwein (Online)
14:25–14:45 Nikhil Balaji
14:45–15:30 Paul Bell
Coffee Break
16:00–16:45 Igor Potapov
16:45–17:30 Joël Ouaknine
Workshop Ends. (ICALP food and drinks event begins.)
Organisers#
- George Kenison (TU Wien)
- Mahsa Shirmohammadi (CNRS, Paris)
Acknowledgements#
We gratefully acknowledge the financial support of both the CNRS and the ANR via the International Emerging Actions grant (IEA'22) and the VeSyAM grant (ANR-22-CE48-0005), respectively.