TY - JOUR
T1 - LOGSPACE AND COMPRESSED-WORD COMPUTATIONS IN NILPOTENT GROUPS
AU - Macdonald, Jeremy
AU - Myasnikov, Alexei
AU - Nikolaev, Andrey
AU - Vassileva, Svetla
N1 - Publisher Copyright:
©2022 American Mathematical Society.
PY - 2022/8/1
Y1 - 2022/8/1
N2 - For finitely generated nilpotent groups, we employ Mal’cev coordinates to solve several classical algorithmic problems efficiently. Computation of normal forms, the membership problem, the conjugacy problem, and computation of presentations for subgroups are solved using only logarithmic space and quasilinear time. Logarithmic space presentation-uniform versions of these algorithms are provided. Compressed-word versions of the same problems, in which each input word is provided as a straight-line program, are solved in polynomial time.
AB - For finitely generated nilpotent groups, we employ Mal’cev coordinates to solve several classical algorithmic problems efficiently. Computation of normal forms, the membership problem, the conjugacy problem, and computation of presentations for subgroups are solved using only logarithmic space and quasilinear time. Logarithmic space presentation-uniform versions of these algorithms are provided. Compressed-word versions of the same problems, in which each input word is provided as a straight-line program, are solved in polynomial time.
UR - http://www.scopus.com/inward/record.url?scp=85137550691&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85137550691&partnerID=8YFLogxK
U2 - 10.1090/tran/8623
DO - 10.1090/tran/8623
M3 - Article
AN - SCOPUS:85137550691
SN - 0002-9947
VL - 375
SP - 5425
EP - 5459
JO - Transactions of the American Mathematical Society
JF - Transactions of the American Mathematical Society
IS - 8
ER -