The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
From MaRDI portal
Publication:408527
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
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
