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 \(aX^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.