ON A GENERALIZATION OF DEHN'S ALGORITHM

DOI10.1142/S0218196708004822MaRDI QIDQ3606403zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Oliver Goodman, Michael Shapiro

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

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)

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.

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 DE number 4016952

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• A NOTE ON CONTEXT-SENSITIVE LANGUAGES AND WORD PROBLEMS
• Automatic structures, rational growth, and geometrically finite hyperbolic groups
• Combination of convergence groups.
• Diophantine geometry over groups. I: Makanin-Razborov diagrams
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• Growing context-sensitive languages and Church-Rosser languages
• Relatively hyperbolic groups: intrinsic geometry, algebraic properties, and algorithmic problems
• SOLVING THE WORD PROBLEM IN REAL TIME
• 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

Cited in

(11)

• The conjugacy problem in groups of non-orientable 3-manifolds
• The generalised word problem in hyperbolic and relatively hyperbolic groups
• 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)