A fast algorithm for Stallings foldings over virtually free groups
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909650494947328 |
|---|---|
| author | Cookson, Sam Touikan, Nicholas |
| author_facet | Cookson, Sam Touikan, Nicholas |
| contents | We give a simple algorithm to solve the subgroup membership problem for virtually free groups. For a fixed virtually free group with a fixed generating set $X$, the subgroup membership problem is uniformly solvable in time $O(n\log^*(n))$ where $n$ is the sum of the word lengths of the inputs with respect to $X$. For practical purposes, this can be considered to be linear time. The algorithm itself is simple and concrete examples are given to show how it can be used for computations in $\mathrm{SL}(2,\mathbb Z)$ and $\mathrm{GL}(2,\mathbb Z)$. We also give an algorithm to decide whether a finitely generated subgroup is isomorphic to a free group. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_00421 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A fast algorithm for Stallings foldings over virtually free groups Cookson, Sam Touikan, Nicholas Group Theory 20F10, 20F65, 68Q25 We give a simple algorithm to solve the subgroup membership problem for virtually free groups. For a fixed virtually free group with a fixed generating set $X$, the subgroup membership problem is uniformly solvable in time $O(n\log^*(n))$ where $n$ is the sum of the word lengths of the inputs with respect to $X$. For practical purposes, this can be considered to be linear time. The algorithm itself is simple and concrete examples are given to show how it can be used for computations in $\mathrm{SL}(2,\mathbb Z)$ and $\mathrm{GL}(2,\mathbb Z)$. We also give an algorithm to decide whether a finitely generated subgroup is isomorphic to a free group. |
| title | A fast algorithm for Stallings foldings over virtually free groups |
| topic | Group Theory 20F10, 20F65, 68Q25 |
| url | https://arxiv.org/abs/2309.00421 |