ON A GENERALIZATION OF DEHN'S ALGORITHM

DOI10.1142/S0218196708004822zbMath1227.20033arXiv0706.3024WikidataQ41997435 ScholiaQ41997435MaRDI QIDQ3606403

Michael Shapiro, Oliver Goodman

Publication date: 26 February 2009

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0706.3024

zbMATH Keywords

word problem; finitely presented groups; finitely generated nilpotent groups; rewriting systems; relatively hyperbolic groups; semigroup generators; Dehn algorithm; Cannon algorithm; rewriting algorithms

Mathematics Subject Classification ID

20F05: Generators, relations, and presentations of groups

20F18: Nilpotent groups

68Q42: Grammars and rewriting systems

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

20F67: Hyperbolic groups and nonpositively curved groups

Related Items

The conjugacy problem in groups of non-orientable 3-manifolds, Homological finiteness properties of monoids, their ideals and maximal subgroups., The generalised word problem in hyperbolic and relatively hyperbolic groups, From automatic structures to automatic groups., Topological finiteness properties of monoids. I: Foundations, GROUPS THAT DO AND DO NOT HAVE GROWING CONTEXT-SENSITIVE WORD PROBLEM

Cites Work

• Unnamed Item
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• Growing context-sensitive languages and Church-Rosser languages
• Combination of convergence groups.
• Diophantine geometry over groups. I: Makanin-Razborov diagrams
• Automatic structures, rational growth, and geometrically finite hyperbolic groups
• SOLVING THE WORD PROBLEM IN REAL TIME
• Relatively hyperbolic groups: intrinsic geometry, algebraic properties, and algorithmic problems
• The complexity of Dehn's algorithm for word problems in groups
• Unsolvable Problems About Small Cancellation and Word Hyperbolic Groups
• A NOTE ON CONTEXT-SENSITIVE LANGUAGES AND WORD PROBLEMS
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM