The submonoid and rational subset membership problems for graph groups.

DOI10.1016/j.jalgebra.2007.08.025zbMath1156.20052arXivmath/0608768OpenAlexW1987543317MaRDI QIDQ947493

Benjamin Steinberg, Markus Lohrey

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

decision problemsgeneralized word problemfinitely presented groupsHNN-extensionsamalgamated free productsregular setsgraph groupsfinitely generated monoidsrational subset membership problemsubmonoid membership problem

Mathematics Subject Classification ID

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

Related Items (19)

SOLUTION OF THE MEMBERSHIP PROBLEM FOR CERTAIN RATIONAL SUBSETS OF ONE-RELATOR GROUPS WITH A SMALL CANCELLATION CONDITION ⋮ Intersection problem for Droms RAAGs ⋮ On the word problem for special monoids ⋮ The emptiness problem for valence automata over graph monoids ⋮ Submonoids and rational subsets of groups with infinitely many ends. ⋮ The fully compressed subgroup membership problem ⋮ Algebraic and context-free subsets of subgroups ⋮ Tilings and submonoids of metabelian groups. ⋮ Knapsack in graph groups ⋮ Recent advances on reachability problems for valence systems (invited talk) ⋮ Fixed points of endomorphisms of trace monoids. ⋮ Bounded Context Switching for Valence Systems ⋮ An automata theoretic approach to the generalized word problem in graphs of groups ⋮ Two problems for solvable and nilpotent groups ⋮ Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups ⋮ New results on the prefix membership problem for one-relator groups ⋮ Free idempotent generated semigroups: the word problem and structure via gain graphs ⋮ Rational subsets of unitriangular groups ⋮ Rational subsets and submonoids of wreath products.

Uses Software

• ALGOL 60

Cites Work

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

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