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

DOI10.1016/J.JALGEBRA.2011.07.024zbMATH Open1248.20038arXiv1102.2481OpenAlexW2060215977MaRDI QIDQ408527FDOQ408527

Authors: Alexander Ushakov, Dong Wook Won, Alexei Myasnikov 

Publication date: 10 April 2012

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

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.

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

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

zbMATH Keywords

computational complexityone-relator groupsword problemBaumslag 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)

Cites Work

• Title not available (Why is that?)
• Word Problems Solvable in Logspace
• Research announcement: The structure of groups with a quasiconvex hierarchy.
• Some two-generator one-relator non-Hopfian groups
• Some results on one-relator groups
• A combination theorem for negatively curved groups
• Combinatorial group theory.
• Residually finite one-relator groups
• Hyperbolic groups and free constructions
• On generalised free products
• THE DOUBLE EXPONENTIAL THEOREM FOR ISODIAMETRIC AND ISOPERIMETRIC FUNCTIONS
• Isoperimetric function of the Baumslag-Gersten group.
• Title not available (Why is that?)
• A non-cyclic one-relator group all of whose finite quotients are cyclic
• Non-linear residually finite groups.
• Reflections on the residual finiteness of one-relator groups.
• On a question of Remeslennikov
• Title not available (Why is that?)
• Dehn's algorithm for the word problem
• On the hyperbolicity of small cancellation groups and one-relator groups
• Power circuits, exponential algebra, and time complexity
• Nonresidually Finite One-Relator Groups
• Generalized Free Products of Linear Groups
• The word problem
• Isoperimetric inequalities for soluble groups

Cited In (19)

• Space functions and space complexity of the word problem in semigroups.
• 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.
• Improved parallel algorithms for generalized Baumslag groups
• Parallel algorithms for power circuits and the word problem of the Baumslag group
• The fully compressed subgroup membership problem
• Exponentially generic subsets of groups
• Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
• Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
• Compressed decision problems in hyperbolic groups
• Complexity of word problems for HNN-extensions
• Complexity of word problems for HNN-extensions
• Compression techniques in group theory
• Space functions of groups.
• The geometry of one-relator groups satisfying a polynomial isoperimetric inequality
• On one-relator groups and units of special one-relation inverse monoids
• Algorithmically complex residually finite groups
• Title not available (Why is that?)
• Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem.

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)