|
| | | | |
| | | |
| Stat |
Members: 3665
Articles: 2'599'751
Articles rated: 2609
25 January 2025 |
|
| | | | |
|
Article overview
| |
|
|
A fast algorithm for Stallings foldings over virtually free groups | | Sam Cookson
; Nicholas Touikan
; | | Date: |
1 Sep 2023 | | Abstract: | 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(nlog^*(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. | | Source: | arXiv, 2309.00421 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER