Rational Subsets of Baumslag-Solitar Groups

We consider the rational subset membership problem for Baumslag-Solitar groups. These groups form a prominent class in the area of algorithmic group theory, and they were recently identified as an obstacle for understanding the rational subsets of $GL(2,\mathbb{Q})$. We show that rational subset membership for Baumslag-Solitar groups $BS(1,q)$ with $q \geq 2$ is decidable and $PSPACE$-complete. To this end, we introduce a word representation of the elements of $BS(1,q)$: their pointed expansion $(PE)$, an annotated $q$-ary expansion. Seeing subsets of $BS(1,q)$ as word languages, this leads to a natural notion of $PE$-regular subsets of $BS(1,q)$: these are the subsets of $BS(1,q)$ whose sets of $PE$ are regular languages. Our proof shows that every rational subset of $BS(1,q)$ is $PE$-regular. Since the class of $PE$-regular subsets of $BS(1,q)$ is well-equipped with closure properties, we obtain further applications of these results. Our results imply that (i) emptiness of Boolean combinations of rational subsets is decidable, (ii) membership to each fixed rational subset of $BS(1,q)$ is decidable in logarithmic space, and (iii) it is decidable whether a given rational subset is recognizable. In particular, it is decidable whether a given finitely generated subgroup of $BS(1,q)$ has finite index.

This is joint work with Michaël Cadilhac and Dmitry Chistikov and has appeared at ICALP 2020. The full version of the paper is available at https://arxiv.org/abs/2006.11898

Date and Venue

Start Date
Online Zoom meeting
End Date


Georg Zetzsche

Speaker's Institution

MPI-SWS, Kaiserslautern, Germany



Semigroups, Automata and Languages