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

DOI10.1145/3373207.3404042MaRDI QIDQ5145996zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

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

Cited in

(2)

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

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)