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 presented groupsHNN-extensionsgraph groupsregular setsfinitely generated monoidsrational subset membership problemsubmonoid membership problemgeneralized word problem

Mathematics Subject Classification ID

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

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.

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
• Publication:4429367
• Two problems for solvable and nilpotent groups
• Publication:4270321

Cites work

• 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?)
• 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
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• Graph groups, coherence, and three-manifolds
• 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

(26)

• FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
• Fixed points of endomorphisms of trace monoids.
• Submonoids and rational subsets of groups with infinitely many ends.
• 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
• An automata theoretic approach to the generalized word problem in graphs of groups.
• The emptiness problem for valence automata over graph monoids
• Algebraic and context-free subsets of subgroups
• Tilings and submonoids of metabelian groups.
• Intersection problem for Droms RAAGs
• The complexity of bidirected reachability in valence systems
• Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups
• On the word problem for special monoids
• On the rational subset problem for groups.
• Two problems for solvable and nilpotent groups
• The power word problem in graph products
• The rational subset membership problem for groups: a survey
• Bounded context switching for valence systems
• New results on the prefix membership problem for one-relator groups
• Rational subsets of unitriangular groups.
• scientific article; zbMATH DE number 2209675 (Why is no real title available?)
• The fully compressed subgroup membership problem
• Knapsack in graph groups
• Free idempotent generated semigroups: the word problem and structure via gain graphs
• Solution of the membership problem for certain rational subsets of one-relator groups with a small cancellation condition.
• Recent advances on reachability problems for valence systems (invited talk)

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)