The complexity of solutions to equations in free groups

GTA Seminar - Wednesday, 24 September, 11:00-12:00 in Carlaw 535A

Please join us for lunch after the talk!

The complexity of solutions to equations in free groups

Murray Elder (Newcastle)

This is joint work with Laura Ciobanu (Neuchatel, Switzerland) and Volker Diekert (Stuttgart, Germany).

An equation in a free group/monoid is an expression like $a{X}^2=XY$, where $a$ is an element of the group/monoid and $X,Y$ are variables. A solution is an assignment of elements to $X$ and $Y$ so that the equation is true in the group/monoid.

Using some clever new results by Diekert, Jez and Plandowski, we are able to describe the set of all solutions to an equation in a free group or free monoid with involution, as a formal language of reasonably low complexity. In my talk I will describe the problem, the relevant formal language classes, and briefly describe how the result works.