Dehn's Algorithm and the Complexity of Word Problems

DOI10.2307/2322385MaRDI QIDQ3826535zbMATH OpenOpenAlexFDO

Authors 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

finite Thue systemlinear-time algorithmrewriting system

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Thue and Post systems, etc. (03D03) Complexity of computation (including implicit computational complexity) (03D15) Word problems, etc. in computability and recursion theory (03D40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Recommendations

• The complexity of Dehn's algorithm for word problems in groups
• ON A GENERALIZATION OF DEHN'S ALGORITHM
• On Dehn presentations and Dehn algorithms
• SOLVING THE WORD PROBLEM IN REAL TIME
• Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems

Cited in

(10)

• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Analysis of Dehn's algorithm by critical pairs
• Complexity, combinatorial group theory and the language of palutators
• Infinite string rewrite systems and complexity
• Reductions and functors from problems to word problems
• Parikh-reducing Church-Rosser representations for some classes of regular languages
• SOLVING THE WORD PROBLEM IN REAL TIME
• The complexity of Dehn's algorithm for word problems in groups
• On some algorithmic problems for groups and monoids
• On the complexity of some extended word problems defined by cancellation rules

This page was built for publication: Dehn's Algorithm and the Complexity of Word Problems

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