11/11/2015 - 15:00

11/11/2015 - 16:00

Speaker:

Svetla Vassileva (Concordia University)

Location:

Burnside Hall, Rm. 920 (McGill University)

Abstract:

The definition of the Grigorchuk group is deceptively simple: it is generated by several actions on an infinite binary tree. However, it satisfies many uncommon properties: for example it has intermediate growth, but is not finitely presentable. In that light, it is interesting to see that many of the classical computational problems are ``easy'' in the Grigorchuk group. The word problem is known to be ``easy'' and we prove the same of the conjugacy problem. Here ``easy'' means log-space (and hence polynomial-time) decidable. We will introduce the Grigorchuk group and the precise notion of log-space decidability in some detail, following which we will discuss algorithms for the solution of the above-mentioned problems