The University of Sydney - School of Mathematics and Statistics

The complexity of solutions to equations in free groups

Murray Elder (Newcastle)

Abstract

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.