Dehn's Algorithm and the Complexity of Word Problems

DOI10.2307/2322385zbMath0673.03028MaRDI QIDQ3826535

Ronald V. Book

Publication date: 1988

Published in: The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2322385

zbMATH Keywords

rewriting system; linear-time algorithm; finite Thue system

Mathematics Subject Classification ID

03-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations

03D15: Complexity of computation (including implicit computational complexity)

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

03D40: Word problems, etc. in computability and recursion theory

03D03: Thue and Post systems, etc.

Related Items

Complexity, combinatorial group theory and the language of palutators, Reductions and functors from problems to word problems