TY - JOUR
T1 - Random van Kampen diagrams and algorithmic problems in groups
AU - Myasnikov, Alexei
AU - Ushakov, Alexander
PY - 2011/5
Y1 - 2011/5
N2 - In this paper we study the structure of random van Kampen diagrams over finitely presented groups. Such diagrams have many remarkable properties. In particular, we show that a random van Kampen diagram over a given group is hyperbolic, even though the group itself may not be hyperbolic. This allows one to design new fast algorithms for the Word Problem in groups. We introduce and study a new filling function, the depth of van Kampen diagrams, - a crucial algorithmic characteristic of null-homotopic words in the group.
AB - In this paper we study the structure of random van Kampen diagrams over finitely presented groups. Such diagrams have many remarkable properties. In particular, we show that a random van Kampen diagram over a given group is hyperbolic, even though the group itself may not be hyperbolic. This allows one to design new fast algorithms for the Word Problem in groups. We introduce and study a new filling function, the depth of van Kampen diagrams, - a crucial algorithmic characteristic of null-homotopic words in the group.
KW - Finitely presented groups
KW - Hyperbolic diagrams
KW - Search algorithms
KW - Todd-coxeter algorithm
KW - Van Kampen diagram
KW - Word Problem
UR - http://www.scopus.com/inward/record.url?scp=84855230176&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84855230176&partnerID=8YFLogxK
U2 - 10.1515/GCC.2011.006
DO - 10.1515/GCC.2011.006
M3 - Article
AN - SCOPUS:84855230176
SN - 1867-1144
VL - 3
SP - 121
EP - 185
JO - Groups, Complexity, Cryptology
JF - Groups, Complexity, Cryptology
IS - 1
ER -