ON A GENERALIZATION OF DEHN'S ALGORITHM.
ON A GENERALIZATION OF DEHN'S ALGORITHM.
复制标题
DOI：
10.1142/s0218196708004822
复制
发表时间：
2008-11-01
影响因子：
0.8
通讯作者：
Shapiro M
中科院分区：
文献类型：
--
作者：
Goodman O;Shapiro M
将Dehn的算法视为一种重写系统，我们推广到允许包含不一定代表群元素的字母的字母表。这将算法解决字问题的群的类别扩展到包括有限生成的幂零群，许多相对双曲群，包括几何有限群和某些几何可分解的3-流形的基本群。该类有几个很好的闭包属性。我们还证明了，如果一个群有一个无限的子群和一个指数增长的子群，并且它们是可交换的，那么它不允许这样的算法。我们把这些算法称为大炮的算法。
Viewing Dehn’s algorithm as a rewriting system, we generalize 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 finitely generated nilpotent groups, many relatively hyperbolic groups including geometrically finite groups and fundamental groups of certain geometrically decomposable 3-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.