The submonoid and rational subset membership problems for graph groups. (Q947493): Difference between revisions

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.