ON A GENERALIZATION OF DEHN'S ALGORITHM

DOI10.1142/S0218196708004822zbMATH Open1227.20033DBLPjournals/ijac/GoodmanS08arXiv0706.3024OpenAlexW2041151288WikidataQ41997435 ScholiaQ41997435MaRDI QIDQ3606403FDOQ3606403

Michael Shapiro, Oliver Goodman

Publication date: 26 February 2009

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

Abstract: Viewing Dehn's algorithm as a rewriting system, we generalise to allow an alphabet containing letters which do not necessarily represent group elements. This extends the class of groups for which the algorithm solves the word problem to include nilpotent groups, many relatively hyperbolic groups including geometrically finite groups and fundamental groups of certain geometrically decomposable manifolds. The class has several nice closure properties. We also show that if a group has an infinite subgroup and one of exponential growth, and they commute, then it does not admit such an algorithm. We dub these Cannon's algorithms.

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

Recommendations

• On Dehn presentations and Dehn algorithms
• A generalisation of the Cantor-Zassenhaus algorithm
• On de Casteljau's algorithm
• On generalizations of the deBruijn-Erdős theorem
• scientific article; zbMATH DE number 5984
• Analysis of Dehn's algorithm by critical pairs
• Dehn's algorithm for simple diagrams
• A generic approach to decomposition algorithms, with an application to digraph decomposition
• scientific article

zbMATH Keywords

finitely generated nilpotent groupsword problemfinitely presented groupsrewriting systemsrelatively hyperbolic groupssemigroup generatorsDehn algorithmCannon algorithmrewriting algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• The generalised word problem in hyperbolic and relatively hyperbolic groups
• The conjugacy problem in groups of non-orientable 3-manifolds
• SOLVING THE WORD PROBLEM IN REAL TIME
• Analysis of Dehn's algorithm by critical pairs
• Homological finiteness properties of monoids, their ideals and maximal subgroups.
• From automatic structures to automatic groups.
• Dehn's Algorithm and the Complexity of Word Problems
• The complexity of Dehn's algorithm for word problems in groups
• On Dehn presentations and Dehn algorithms
• GROUPS THAT DO AND DO NOT HAVE GROWING CONTEXT-SENSITIVE WORD PROBLEM
• Topological finiteness properties of monoids. I: Foundations

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

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