$k$-regular sequences: Asymptotics and Decidability

Daniel Krenn (Universität Salzburg)

01-Mar-2022, 13:30-14:30 (2 years ago)

Abstract: A sequence $x(n)$ is called $k$-regular, if the set of subsequences $x(k^j n + r)$ is contained in a finitely generated module. In this talk, we will consider the asymptotic growth of $k$-regular sequences. When is it possible to compute it? ...and when not? If possible, how precisely can we compute it? If not, is it just a lack of methods or are the underlying decision questions recursively solvable (i.e., decidable in a computational sense)? We will discuss answers to these questions. To round off the picture, we will consider further decidability questions around $k$-regular sequences and the subclass of $k$-automatic sequences.

This is based on joint works with Clemens Heuberger and with Jeffrey Shallit.

dynamical systemsnumber theory

Audience: researchers in the topic

( paper | slides )


One World Numeration seminar

Series comments: Description: Online seminar on numeration systems and related topics

For questions or subscribing to the mailing list, contact the organisers at numeration@irif.fr

Organizers: Shigeki Akiyama, Ayreena Bakhtawar, Karma Dajani, Kevin Hare, Hajime Kaneko, Niels Langeveld, Lingmin Liao, Wolfgang Steiner*
*contact for this listing

Export talk to