Rational subsets of Baumslag-Solitar groups
M Cadilhac, D Chistikov, G Zetzsche - arXiv preprint arXiv:2006.11898, 2020 - arxiv.org
M Cadilhac, D Chistikov, G Zetzsche
arXiv preprint arXiv:2006.11898, 2020•arxiv.orgWe 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 $\text
{GL}(2,\mathbb {Q}) $. We show that rational subset membership for Baumslag-Solitar
groups $\text {BS}(1, q) $ with $ q\ge 2$ is decidable and PSPACE-complete. To this end,
we introduce a word representation of the elements of $\text {BS}(1, q) $: their pointed …
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 $\text
{GL}(2,\mathbb {Q}) $. We show that rational subset membership for Baumslag-Solitar
groups $\text {BS}(1, q) $ with $ q\ge 2$ is decidable and PSPACE-complete. To this end,
we introduce a word representation of the elements of $\text {BS}(1, q) $: their pointed …
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 . We show that rational subset membership for Baumslag-Solitar groups with is decidable and PSPACE-complete. To this end, we introduce a word representation of the elements of : their pointed expansion (PE), an annotated -ary expansion. Seeing subsets of as word languages, this leads to a natural notion of PE-regular subsets of : these are the subsets of whose sets of PE are regular languages. Our proof shows that every rational subset of is PE-regular. Since the class of PE-regular subsets of 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 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 has finite index.
arxiv.org