ON A GENERALIZATION OF DEHN'S ALGORITHM

DOI10.1142/S0218196708004822zbMath1227.20033DBLPjournals/ijac/GoodmanS08arXiv0706.3024OpenAlexW2041151288WikidataQ41997435 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 problemfinitely presented groupsfinitely generated nilpotent groupsrewriting systemsrelatively hyperbolic groupssemigroup generatorsDehn algorithmCannon algorithmrewriting algorithms

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Nilpotent groups (20F18) Grammars and rewriting systems (68Q42) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67)

Related Items (6)

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

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

This page was built for publication: ON A GENERALIZATION OF DEHN'S ALGORITHM