Linear time algorithm for the conjugacy problem in the first Grigorchuk group

Mitra Modi; Mathew Seedhom; Alexander Ushakov

doi:10.1142/S0218196721500363

Linear time algorithm for the conjugacy problem in the first Grigorchuk group

Mitra Modi
, Mathew Seedhom
, Alexander Ushakov

Department of Mathematical Sciences

Stevens Institute of Technology

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	789-806
Number of pages	18
Journal	International Journal of Algebra and Computation
Volume	31
Issue number	4
DOIs	https://doi.org/10.1142/S0218196721500363
State	Published - Jun 2021

Keywords

Grigorchuk group
complexity
conjugacy problem
word problem

Access to Document

10.1142/S0218196721500363

Cite this

@article{323e72317cf0479c8ac4015499f52335,

title = "Linear time algorithm for the conjugacy problem in the first Grigorchuk group",

abstract = "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.",

keywords = "Grigorchuk group, complexity, conjugacy problem, word problem",

author = "Mitra Modi and Mathew Seedhom and Alexander Ushakov",

note = "Publisher Copyright: {\textcopyright} 2021 World Scientific Publishing Company.",

year = "2021",

month = jun,

doi = "10.1142/S0218196721500363",

language = "English",

volume = "31",

pages = "789--806",

number = "4",

}

TY - JOUR

T1 - Linear time algorithm for the conjugacy problem in the first Grigorchuk group

AU - Modi, Mitra

AU - Seedhom, Mathew

AU - Ushakov, Alexander

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 - https://www.scopus.com/pages/publications/85107729696

UR - https://www.scopus.com/pages/publications/85107729696#tab=citedBy

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 -

Linear time algorithm for the conjugacy problem in the first Grigorchuk group

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this