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

DOI10.1016/0196-6774(85)90031-8MaRDI QIDQ3718927zbMATH OpenOpenAlexFDO

Authors Boris Iosifovic Domanskii, Michael Anshel

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

Turing machineword problemDehn's algorithmDA-group

Mathematics Subject Classification ID

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

Recommendations

• Dehn's Algorithm and the Complexity of Word Problems
• SOLVING THE WORD PROBLEM IN REAL TIME
• On Dehn functions of infinite presentations of groups.
• On Dehn presentations and Dehn algorithms
• ON A GENERALIZATION OF DEHN'S ALGORITHM

Cited in

(17)

• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Thue systems as rewriting systems
• SOLVING THE WORD PROBLEM IN REAL TIME
• Polynomial-time proofs that groups are hyperbolic
• A catalogue of complete group presentations
• Complexity, combinatorial group theory and the language of palutators
• ON REAL-TIME WORD PROBLEMS
• Average-case complexity and decision problems in group theory.
• The Compressed Word Problem for Groups
• The word problem in Hanoi Towers groups.
• Some geodesic problems in groups
• Dehn's Algorithm and the Complexity of Word Problems
• ON A GENERALIZATION OF DEHN'S ALGORITHM
• scientific article; zbMATH DE number 3877408 (Why is no real title available?)
• scientific article; zbMATH DE number 3993567 (Why is no real title available?)
• Generic-case complexity, decision problems in group theory, and random walks.

This page was built for publication: The complexity of Dehn's algorithm for word problems in groups

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