The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.

DOI10.1016/j.jalgebra.2011.07.024zbMath1248.20038arXiv1102.2481OpenAlexW2060215977MaRDI QIDQ408527

Alexander Ushakov, Dong Wook Won, Alexei G. Myasnikov

Publication date: 10 April 2012

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

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

zbMATH Keywords

computational complexityword problemone-relator groupsBaumslag groups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem ⋮ The geometry of one-relator groups satisfying a polynomial isoperimetric inequality ⋮ Algorithmically complex residually finite groups ⋮ Space functions and space complexity of the word problem in semigroups. ⋮ The fully compressed subgroup membership problem ⋮ Parallel algorithms for power circuits and the word problem of the Baumslag group ⋮ Improved parallel algorithms for generalized Baumslag groups ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ EFFICIENT ALGORITHMS FOR HIGHLY COMPRESSED DATA: THE WORD PROBLEM IN HIGMAN'S GROUP IS IN P ⋮ Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P ⋮ Exponentially generic subsets of groups ⋮ Unnamed Item ⋮ Conjugacy in Baumslag's group, generic case complexity, and division in power circuits ⋮ Complexity of word problems for HNN-extensions ⋮ Complexity of word problems for HNN-extensions ⋮ Space functions of groups ⋮ On one-relator groups and units of special one-relation inverse monoids ⋮ Compression techniques in group theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A combination theorem for negatively curved groups
• On generalised free products
• Research announcement: The structure of groups with a quasiconvex hierarchy.
• Combinatorial group theory.
• Non-linear residually finite groups.
• Reflections on the residual finiteness of one-relator groups.
• Dehn's algorithm for the word problem
• THE DOUBLE EXPONENTIAL THEOREM FOR ISODIAMETRIC AND ISOPERIMETRIC FUNCTIONS
• Some two-generator one-relator non-Hopfian groups
• Word Problems Solvable in Logspace
• Hyperbolic groups and free constructions
• On the hyperbolicity of small cancellation groups and one-relator groups
• POWER CIRCUITS, EXPONENTIAL ALGEBRA, AND TIME COMPLEXITY
• Residually finite one-relator groups
• Some results on one-relator groups
• A non-cyclic one-relator group all of whose finite quotients are cyclic
• Nonresidually Finite One-Relator Groups
• Generalized Free Products of Linear Groups
• The word problem
• Isoperimetric inequalities for soluble groups