Presented by:
Murray Elder, The University of Newcastle
Date:
Tue 18 Aug, 3:00 am - 4:00 am
Venue:
Building 67, Room 442

An equation in a free group is an expression like $aXY=bX$
where a,b are elements of the free group, and $X,Y$ are {\em variables}.
A solution is an assignment $X\mapsto u, Y\mapsto v$ with $u,v$ elements of the free group so that $auv=bu$ holds.

(Exercise: can you find a solution to $aXY=bX$? Hint, $X$ could start with $a^{-1}$ for example.)

In this new work we show that the set of all solutions to any equation in a free group can be found in a space-efficient way. We describe all solutions using a finite directed graph, and this graph can be constructed
by a nondeterministic algorithm that uses $n\log n$ space where $n$ is the length of the equation plus the rank of the free group.

In my talk I will try to motivate the problem, explain some of the previous attempts at understanding solutions, and give a brief idea of our proof.

This is joint work with Laura Ciobanu, Université de Neuchâtel, Switzerland
and Volker Diekert, Universität Stuttgart, Germany.