# Finding all solutions to an equation in a free group in NSPACE(nlog n)

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.

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.