SMS scnews item created by Stephan Tillmann at Mon 22 Sep 2014 1336
Type: Seminar
Distribution: World
Expiry: 22 Dec 2014
Calendar1: 24 Sep 2014 1100-1200
CalLoc1: Carslaw 535A
Auth: tillmann@p710.pc (assumed)

The complexity of solutions to equations in free groups

Murray Elder

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

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 $$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.

Actions: