论文标题
第一个Grigorchuk组中共轭问题的线性时间算法
Linear time algorithm for the conjugacy problem in the first Grigorchuk group
论文作者
论文摘要
我们证明，第一个Grigorchuck组$γ$中的共轭问题可以在线性时间解决。此外，确定元素列表$ w_1，\ ldots，w_k \inγ$是否包含一对共轭元素的问题可以在线性时间内解决。我们还表明，在多项式时间内可以找到一对共轭元素$ u，v \inγ$的共轭器。
We prove that the conjugacy problem in the first Grigorchuck group $Γ$ can be solved in linear time. Furthermore, the problem to decide if a list of elements $w_1,\ldots,w_k\inΓ$ contains a pair of conjugate elements can be solved in linear time. We also show that a conjugator for a pair of conjugate element $u,v\inΓ$ can be found in polynomial time.
