LOGSPACE AND COMPRESSED-WORD COMPUTATIONS IN NILPOTENT GROUPS

Jeremy Macdonald, Alexei Myasnikov, Andrey Nikolaev, Svetla Vassileva

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)5425-5459
Number of pages35
JournalTransactions of the American Mathematical Society
Volume375
Issue number8
DOIs
StatePublished - 1 Aug 2022

Fingerprint

Dive into the research topics of 'LOGSPACE AND COMPRESSED-WORD COMPUTATIONS IN NILPOTENT GROUPS'. Together they form a unique fingerprint.

Cite this