Murray Elder, Ph.D.


Equations in Groups

An equation in a group or monoid is simply a pair of words over variables X,Y,Z,... and elements of the group/monoid. For example, an equation in the free monoid \left\{a,b\right\}^\ast might be
aaX=Ybb. A solution to an equation is a mapping X\mapsto u,Y\mapsto v so that replacing variables by group/monoid elements in the equation makes the left and right sides equal. In our example, X\mapsto bb and Y\mapsto aa is one possible solution (in the free monoid, the two sides are equal if and only if they are identical as words, but in other monoids and groups this is not necessarily true). (Exercise: are there any other solutions?)

Makanin gave a complicated algorithm to decide whether or not an arbitrary equation in a free monoid had a solution in 1977. In 1983 he extended the result to equations in free groups. Rips and Sela extended this further to hyperbolic groups without torsion, and in 2010 Dahmani and Guirardel to all hyperbolic groups.

In my talk I will describe work of many authors, coming from Computer Science, to not only decide but find all possible solutions to an equation in a free monoid/group in extremely low space complexity. Moreover the new algorithms give a relatively simple description (as a formal language) of the solution set.

My results are joint with Laura Ciobanu (Heriot-Watt) and Volker Diekert (Stuttgart).