The submonoid and rational subset membership problems for graph groups
| dc.creator | Lohrey, Markus | |
| dc.creator | Steinberg, Benjamin | |
| dc.date | 2006-08-30 | |
| dc.date | 2007-07-19 | |
| dc.date.accessioned | 2026-07-07T08:19:08Z | |
| dc.date.available | 2026-07-07T08:19:08Z | |
| dc.description | We show that the membership problem in a finitely generated submonoid of a graph group (also called a right-angled Artin group or a free partially commutative group) is decidable if and only if the independence graph (commutation graph) is a transitive forest. As a consequence we obtain the first example of a finitely presented group with a decidable generalized word problem that does not have a decidable membership problem for finitely generated submonoids. We also show that the rational subset membership problem is decidable for a graph group if and only if the independence graph is a transitive forest, answering a question of Kambites, Silva, and the second author. Finally we prove that for certain amalgamated free products and HNN-extensions the rational subset and submonoid membership problems are recursively equivalent. In particular, this applies to finitely generated groups with two or more ends that are either torsion-free or residually finite. | |
| dc.identifier | https://arxiv.org/abs/math/0608768 | |
| dc.identifier | http://arxiv.org/abs/math/0608768 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134668 | |
| dc.subject | Group Theory | |
| dc.subject | 20F10 | |
| dc.title | The submonoid and rational subset membership problems for graph groups | |
| dc.type | text |