Finite automata for Schreier graphs of virtually free groups
Finite automata for Schreier graphs of virtually free groups
复制标题
几乎自由群的 Schreier 图的有限自动机
DOI：
10.1515/jgth-2015-0028
复制
发表时间：
2011
影响因子：
0.5
通讯作者：
E. Ventura
中科院分区：
文献类型：
--
作者：
Pedro V. Silva;X. Soler;E. Ventura
摘要 f.g. 的 Stallings 结构。通过引入 Stallings 部分的概念来推广自由群的子群，它允许基于边缘折叠来有效计算 Schreier 图的核心。事实证明，承认斯托林斯部分的群体正是 f.g.。几乎自由的群体，这是通过基于巴斯-塞尔理论的建设性方法证明的。还讨论了复杂性问题和应用。
Abstract The Stallings construction for f.g. subgroups of free groups is generalized by introducing the concept of Stallings section, which allows efficient computation of the core of a Schreier graph based on edge folding. It is proved that the groups that admit Stallings sections are precisely the f.g. virtually free groups, this is proved through a constructive approach based on Bass–Serre theory. Complexity issues and applications are also discussed.