Detecting Fully Irreducible Automorphisms: A Polynomial Time Algorithm
Detecting Fully Irreducible Automorphisms: A Polynomial Time Algorithm
复制标题
检测完全不可约自同构：多项式时间算法
DOI：
10.1080/10586458.2017.1326326
复制
发表时间：
2019
影响因子：
0.5
通讯作者：
Bell, Mark C.
中科院分区：
文献类型：
--
作者：
Kapovich, Ilya;Bell, Mark C.
在本文中，我们提出了一种算法来确定一个元素是否为iwip（“完全不可约”）自同构。在某些方面，该算法相当低效，因为它涉及一些一般的枚举过程以及并行运行几个抽象进程。在本文中，我们通过消除这些效率低下的特征以及消除任何映射类组算法的使用来改进算法。我们的主要结果是产生，对于任何固定n大于或等于3，一个算法，给定一个元素φ的拓扑代表，在多项式时间内根据“大小”决定是否φ是完全不可约的。此外，我们还提供了一个完全不可约的火车轨道判据，该判据涵盖了的所有完全不可约元素，包括阿托向和非阿托向元素。我们也给出了一种替代Turner的算法，用于在扩展的火车轨道地图中找到所有不可分割的尼尔森路径，并估计了该算法的复杂度。Mark Bell的附录给出了Bestvina-Handel算法的复杂度的一个多项式上界，根据拓扑代表的大小，用于寻找不可约的火车轨道代表或拓扑约简。
In we produced an algorithm for deciding whether or not an elementis an iwip (“fully irreducible”) automorphism. At several points that algorithm was rather inefficient as it involved some general enumeration procedures as well as running several abstract processes in parallel. In this article we refine the algorithm from by eliminating these inefficient features, and also by eliminating any use of mapping class groups algorithms. Our main result is to produce, for any fixedN⩾ 3, an algorithm which, given a topological representativefof an element ϕ of, decides in polynomial time in terms of the “size” off, whether or not ϕ is fully irreducible. In addition, we provide a train-track criterion of being fully irreducible which covers all fully irreducible elements of, including both atoroidal and non-atoroidal ones. We also give an algorithm, alternative to that of Turner, for finding all the indivisible Nielsen paths in an expanding train-track map, and estimate the complexity of this algorithm. An Appendix by Mark Bell provides a polynomial upper bound, in terms of the size of the topological representative, on the complexity of the Bestvina–Handel algorithm for finding either an irreducible train-track representative or a topological reduction.
登录
查看更多内容
关于怀特海最小化问题的复杂性
影响因子：
0.8
作者：
Abdó Roig;E. Ventura;P. Weil
通讯作者：
P. Weil
Out (F~n) I 的 Tits 替代方案：指数增长自同构的动力学
DOI：
--
发表时间：
1997
期刊：
影响因子：
--
作者：
M. Bestvina;Mark Feighn;M. Handel
通讯作者：
M. Handel
DOI：
10.1142/s0218196797000137
发表时间：
1996-12
期刊：
Int. J. Algebra Comput.
影响因子：
--
作者：
Rita Gitik
通讯作者：
Rita Gitik
无循环群的 McMullen 多项式和 Lipschitz 流
影响因子：
2.6
作者：
Dowdall, Spencer;Kapovich, Ilya;Leininger, Christopher
通讯作者：
Leininger, Christopher
自由群的叠片、树和不可约自同构
DOI：
--
发表时间：
1997
期刊：
影响因子：
--
作者：
M. Bestvina;Mark Feighn;M. Handel
通讯作者：
M. Handel