TY - JOUR
T1 - Linear time algorithm for the conjugacy problem in the first Grigorchuk group
AU - Modi, Mitra
AU - Seedhom, Mathew
AU - Ushakov, Alexander
N1 - Publisher Copyright:
© 2021 World Scientific Publishing Company.
PY - 2021/6
Y1 - 2021/6
N2 - We prove that the conjugacy problem in the first Grigorchuk group can be solved in linear time. Furthermore, the problem to decide if a list of elements w1, wk 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 can be found in polynomial time.
AB - We prove that the conjugacy problem in the first Grigorchuk group can be solved in linear time. Furthermore, the problem to decide if a list of elements w1, wk 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 can be found in polynomial time.
KW - Grigorchuk group
KW - complexity
KW - conjugacy problem
KW - word problem
UR - http://www.scopus.com/inward/record.url?scp=85107729696&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85107729696&partnerID=8YFLogxK
U2 - 10.1142/S0218196721500363
DO - 10.1142/S0218196721500363
M3 - Article
AN - SCOPUS:85107729696
SN - 0218-1967
VL - 31
SP - 789
EP - 806
JO - International Journal of Algebra and Computation
JF - International Journal of Algebra and Computation
IS - 4
ER -