The submonoid and rational subset membership problems for graph groups.

DOI10.1016/J.JALGEBRA.2007.08.025MaRDI QIDQ947493zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, Benjamin Steinberg

Publication date 6 October 2008

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0608768

zbMATH Keywords

amalgamated free productsdecision problemsfinitely generated monoidsfinitely presented groupsgeneralized word problemgraph groupsHNN-extensionsrational subset membership problemregular setssubmonoid membership problem

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Braid groups; Artin groups (20F36) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Abstract: 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.

Review text

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.

Recommendations

• Submonoids and rational subsets of groups with infinitely many ends.
• The rational subset membership problem for groups: a survey
• Tilings and submonoids of metabelian groups.
• On the rational subset problem for groups.
• On decidability of amenability in computable groups
• scientific article; zbMATH DE number 1985667
• Two problems for solvable and nilpotent groups
• scientific article; zbMATH DE number 1361364

Cites work

• A Note on "The Comparability Graph of a Tree"
• Bounded Algol-Like Languages
• Characterizations of the decidability of some problems for regular trace languages
• Combinatorics on traces
• Connectivity at infinity for right angled Artin groups
• Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups.
• FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
• FOR REWRITING SYSTEMS THE TOPOLOGICAL FINITENESS CONDITIONS FDT AND FHT ARE NOT EQUIVALENT
• Graph groups, coherence, and three-manifolds
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• scientific article; zbMATH DE number 1985667 (Why is no real title available?)
• scientific article; zbMATH DE number 1842475 (Why is no real title available?)
• scientific article; zbMATH DE number 848082 (Why is no real title available?)
• scientific article; zbMATH DE number 1421185 (Why is no real title available?)
• scientific article; zbMATH DE number 3257446 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3381557 (Why is no real title available?)
• scientific article; zbMATH DE number 2209675 (Why is no real title available?)
• scientific article; zbMATH DE number 2221703 (Why is no real title available?)
• Morse theory and finiteness properties of groups
• On Context-Free Languages
• On the profinite topology of right-angled Artin groups.
• On the rational subset problem for groups.
• Rational sets in commutative monoids
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
• Subgroup separability, knot groups and graph manifolds
• The geometry and topology of reconfiguration
• The word problem for free partially commutative groups
• Word problems over traces which are solvable in linear time

Cited in

(35)

• Knapsack in graph groups
• Two problems for solvable and nilpotent groups
• Free idempotent generated semigroups: the word problem and structure via gain graphs
• On the word problem for special monoids
• Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups
• On finitely generated submonoids of virtually free groups
• The emptiness problem for valence automata over graph monoids
• Recent advances on reachability problems for valence systems (invited talk)
• The rational subset membership problem for groups: a survey
• Solution of the membership problem for certain rational subsets of one-relator groups with a small cancellation condition.
• New results on the prefix membership problem for one-relator groups
• Intersection problem for Droms RAAGs
• Fixed points of endomorphisms of trace monoids.
• FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
• Bounded context switching for valence systems
• An automata theoretic approach to the generalized word problem in graphs of groups.
• Rational subsets of unitriangular groups.
• scientific article; zbMATH DE number 2209675 (Why is no real title available?)
• The fully compressed subgroup membership problem
• Submonoids and rational subsets of groups with infinitely many ends.
• Algebraic and context-free subsets of subgroups
• Tilings and submonoids of metabelian groups.
• The power word problem in graph products
• The complexity of bidirected reachability in valence systems
• Decidability of membership problems for flat rational subsets of \(\mathrm{GL}(2,\mathbb{Q})\) and singular matrices
• Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests
• The submonoid and rational subset membership problems for Artin groups
• Membership problems in braid groups and Artin groups
• Membership problems in nilpotent groups
• Subsets of groups in public-key cryptography
• Membership problems in infinite groups
• Membership problems for positive one-relator groups and one-relation monoids
• On subgroup separability and membership problems in twisted right-angled Artin groups
• Submonoid membership in n-dimensional lamplighter groups and S-unit equations
• On the rational subset problem for groups.

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: The submonoid and rational subset membership problems for graph groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q947493)