The submonoid and rational subset membership problems for graph groups. (Q947493): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: ALGOL 60 / rank | |||
Normal rank |
Revision as of 14:11, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The submonoid and rational subset membership problems for graph groups. |
scientific article |
Statements
The submonoid and rational subset membership problems for graph groups. (English)
0 references
6 October 2008
0 references
A natural generalization of the word and generalized word problem is the submonoid membership problem: given a finite set \(S\) of elements of \(G\) and an element \(g\in G\), does \(g\) belong to the submonoid generated by \(S\)? A further generalization is the rational subset membership problem: for a given rational subset \(L\) of a group \(G\) and \(g\in G\), it is asked whether \(g\in L\). In this amazing paper the authors show that the membership problem in a finitely generated submonoid of a graph group is decidable if and only if the independence graph is a transitive forest and hence they 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. As another important point, they give a necessary and sufficient condition for a graph group to have decidable rational subset problem. Therefore, they answer a question asked by Kambites, Silva and the second author [\textit{M. Kambites, P. V. Silva, B. Steinberg}, J. Algebra 309, No. 2, 622-639 (2007; Zbl 1123.20047)]. At the end of the paper, the authors call the attention to recursive equivalence of the rational subset and submonoid membership problems for certain amalgamated free products and HNN-extensions.
0 references
decision problems
0 references
graph groups
0 references
regular sets
0 references
generalized word problem
0 references
submonoid membership problem
0 references
rational subset membership problem
0 references
finitely generated monoids
0 references
finitely presented groups
0 references
amalgamated free products
0 references
HNN-extensions
0 references