The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
From MaRDI portal
(Redirected from Publication:408527)
Abstract: We prove that the Word problem in the Baumslag group G(1,2) which has a non-elementary Dehn function is decidable in polynomial time.
Recommendations
- Groups with undecidable word problem and almost quadratic Dehn function. (With an appendix written by M. V. Sapir)
- The conjugacy problem in the Grigorchuk group is polynomial time decidable.
- The complexity of Dehn's algorithm for word problems in groups
- HOMOLOGICAL DECISION PROBLEMS FOR FINITELY GENERATED GROUPS WITH SOLVABLE WORD PROBLEM
- On complexity of the word problem in braid groups and mapping class groups
- Solvable groups with polynomial Dehn functions
- Polynomially-bounded Dehn functions of groups
- The word problem of the Brin-Thompson group is \textsf{coNP}-complete
- Groups with decidable word problem that do not embed in groups with decidable conjugacy problem
- On parameterized complexity of the word search problem in the Baumslag-Gersten group
Cites work
- scientific article; zbMATH DE number 1819874 (Why is no real title available?)
- scientific article; zbMATH DE number 53661 (Why is no real title available?)
- scientific article; zbMATH DE number 67432 (Why is no real title available?)
- A combination theorem for negatively curved groups
- A non-cyclic one-relator group all of whose finite quotients are cyclic
- Combinatorial group theory.
- Dehn's algorithm for the word problem
- Generalized Free Products of Linear Groups
- Hyperbolic groups and free constructions
- Isoperimetric function of the Baumslag-Gersten group.
- Isoperimetric inequalities for soluble groups
- Non-linear residually finite groups.
- Nonresidually Finite One-Relator Groups
- On a question of Remeslennikov
- On generalised free products
- On the hyperbolicity of small cancellation groups and one-relator groups
- Power circuits, exponential algebra, and time complexity
- Reflections on the residual finiteness of one-relator groups.
- Research announcement: The structure of groups with a quasiconvex hierarchy.
- Residually finite one-relator groups
- Some results on one-relator groups
- Some two-generator one-relator non-Hopfian groups
- THE DOUBLE EXPONENTIAL THEOREM FOR ISODIAMETRIC AND ISOPERIMETRIC FUNCTIONS
- The word problem
- Word Problems Solvable in Logspace
Cited in
(17)- Compression techniques in group theory
- Exponentially generic subsets of groups
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- Parallel algorithms for power circuits and the word problem of the Baumslag group
- The geometry of one-relator groups satisfying a polynomial isoperimetric inequality
- Efficient algorithms for highly compressed data: the word problem in Higman's group is in P.
- Space functions and space complexity of the word problem in semigroups.
- Compressed decision problems in hyperbolic groups
- Improved parallel algorithms for generalized Baumslag groups
- Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
- On one-relator groups and units of special one-relation inverse monoids
- Space functions of groups.
- Algorithmically complex residually finite groups
- The fully compressed subgroup membership problem
- Complexity of word problems for HNN-extensions
- Complexity of word problems for HNN-extensions
- scientific article; zbMATH DE number 7559146 (Why is no real title available?)
This page was built for publication: The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q408527)
