The submonoid and rational subset membership problems for graph groups. (Q947493)

From MaRDI portal
Revision as of 18:55, 19 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references