标题： 斯托林斯折叠与有限群的并接子群 显示英文标题

标题： Stallings' Foldings and Subgroups of Amalgams of Finite Groups

摘要： 在20世纪80年代，Stallings证明了自由群的每一个有限生成子群都可以通过一个有限最小浸入的圆环束进行规范表示。 从自动机理论的角度来看，这是一个最小的有限逆自动机。 这使得可以利用有限自动机和有限逆半群的深入算法理论来回答关于自由群的有限生成子群的问题。 在本文中，我们尝试将相同的方法应用于其他类型的群。 一个基本的新问题是必须对Stallings折叠算法进行修改，以允许“缝合”非自由群的关系。 我们研究了有限群的并接群类。 已知这些群是局部拟凸的，因此所有有限生成子群都可以由有限自动机表示。 我们提出了一种计算此类有限自动机的算法，并用它来解决各种算法问题。 显示英文摘要

摘要： In the 1980's Stallings showed that every finitely generated subgroup of a free group is canonically represented by a finite minimal immersion of a bouquet of circles. In terms of the theory of automata, this is a minimal finite inverse automaton. This allows for the deep algorithmic theory of finite automata and finite inverse monoids to be used to answer questions about finitely generated subgroups of free groups. In this paper we attempt to apply the same methods to other classes of groups. A fundamental new problem is that the Stallings folding algorithm must be modified to allow for ``sewing'' on relations of non-free groups. We look at the class of groups that are amalgams of finite groups. It is known that these groups are locally quasiconvex and thus all finitely generated subgroups are represented by finite automata. We present an algorithm to compute such a finite automaton and use it to solve various algorithmic problems.