The complexity of Dehn's algorithm for word problems in groups

DOI10.1016/0196-6774(85)90031-8zbMath0591.20037OpenAlexW1972468537MaRDI QIDQ3718927

Michael Anshel, Boris Iosifovic Domanskii

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/0196-6774(85)90031-8

zbMATH Keywords

word problemTuring machineDehn's algorithmDA-group

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Related Items

WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM, A catalogue of complete group presentations, Thue systems as rewriting systems, Complexity, combinatorial group theory and the language of palutators, Generic-case complexity, decision problems in group theory, and random walks., Polynomial-time proofs that groups are hyperbolic, Average-case complexity and decision problems in group theory., ON A GENERALIZATION OF DEHN'S ALGORITHM