Automatic Presentations for Finitely Generated Groups
Automatic Presentations for Finitely Generated Groups
复制标题
有限生成群的自动演示
DOI：
10.1007/978-3-540-31856-9_57
复制
发表时间：
2005
影响因子：
0.9
通讯作者：
R. Thomas
中科院分区：
文献类型：
--
作者：
G. Oliver;R. Thomas
一个结构被称为可计算的，如果它的定义域可以用图灵机接受的集合来表示，并且如果它的关系可以用图灵机来检查。将这个定义中的图灵机限制为有限自动机，我们得到了一类具有特别简单的计算结构的结构;这些结构被称为具有自动表示。鉴于其良好的算法特性，这些算法在各种领域都受到了关注。
一个特别感兴趣的领域是自动结构的分类。我们考虑的一个主要例子是群类。我们给出了一个完整的刻画的情况下，生成的群体，并表明，这样一个群体有一个自动介绍，当且仅当它是几乎阿贝尔。
A structure is said to be computable if its domain can be represented by a set which is accepted by a Turing machine and if its relations can then be checked using Turing machines. Restricting the Turing machines in this definition to finite automata gives us a class of structures with a particularly simple computational structure; these structures are said to have automatic presentations. Given their nice algorithmic properties, these have been of interest in a wide variety of areas.
An area of particular interest has been the classification of automatic structures. One of the prime examples under consideration has been the class of groups. We give a complete characterization in the case of finitely generated groups and show that such a group has an automatic presentation if and only if it is virtually abelian.