On parameterized complexity of the word search problem in the Baumslag-Gersten group

DOI10.1145/3373207.3404042OpenAlexW3046140887WikidataQ130991637 ScholiaQ130991637MaRDI QIDQ5145996FDOQ5145996

Authors:

Publication date: 22 January 2021

Published in: Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3373207.3404042

Recommendations

• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• The Bounded and Precise Word Problems for Presentations of Groups
• The complexity of Dehn's algorithm for word problems in groups
• Parallel algorithms for power circuits and the word problem of the Baumslag group

zbMATH Keywords

parameterized complexityword problemfixed parameter tractabilityBaumslag-Solitar groupDehn functionBaumslag-Gersten groupword search problem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Cited In (2)

• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Parallel algorithms for power circuits and the word problem of the Baumslag group

This page was built for publication: On parameterized complexity of the word search problem in the Baumslag-Gersten group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145996)