SOLVING THE WORD PROBLEM IN REAL TIME

DOI10.1017/S0024610701002083zbMath1032.20022MaRDI QIDQ3151018

Derek F. Holt, Sarah Rees

Publication date: 22 October 2002

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

word problemword-hyperbolic groupsDehn algorithmsreal-time Turing machines

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67) Word problems, etc. in computability and recursion theory (03D40) Cancellation theory of groups; application of van Kampen diagrams (20F06)

Related Items

Polynomial time conjugacy in wreath products and free solvable groups, Logspace and compressed-word computations in nilpotent groups, Generic-case complexity, decision problems in group theory, and random walks., Knapsack problems in products of groups, ON A GENERALIZATION OF DEHN'S ALGORITHM, The generalised word problem in hyperbolic and relatively hyperbolic groups, Knapsack problems in groups, Asymptotic invariants, complexity of groups and related problems