TY - JOUR
T1 - Cyclic rewriting and conjugacy problems
AU - Diekert, Volker
AU - Duncan, Andrew
AU - Myasnikov, Alexei G.
PY - 2012/12
Y1 - 2012/12
N2 - Cyclic words are equivalence classes of cyclic permutations of ordinary words. When a group is given by a rewriting relation, a rewriting system on cyclic words is induced, which is used to construct algorithms to find minimal length elements of conjugacy classes in the group. These techniques are applied to the universal groups of Stallings pregroups and in particular to free products with amalgamation, HNN-extensions and virtually free groups, to yield simple and intuitive algorithms and proofs of conjugacy criteria.
AB - Cyclic words are equivalence classes of cyclic permutations of ordinary words. When a group is given by a rewriting relation, a rewriting system on cyclic words is induced, which is used to construct algorithms to find minimal length elements of conjugacy classes in the group. These techniques are applied to the universal groups of Stallings pregroups and in particular to free products with amalgamation, HNN-extensions and virtually free groups, to yield simple and intuitive algorithms and proofs of conjugacy criteria.
KW - Algorithmic group theory
KW - Conjugacy problem
KW - Free product with amalgamation
KW - HNN-extension
KW - Rewriting system
KW - Stallings pregroup
UR - http://www.scopus.com/inward/record.url?scp=84872945766&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84872945766&partnerID=8YFLogxK
U2 - 10.1515/gcc-2012-0020
DO - 10.1515/gcc-2012-0020
M3 - Article
AN - SCOPUS:84872945766
SN - 1867-1144
VL - 4
SP - 321
EP - 355
JO - Groups, Complexity, Cryptology
JF - Groups, Complexity, Cryptology
IS - 2
ER -