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)

Geometry-Topology-Analysis Seminar

The complexity of solutions to equations in free groups

Murray Elder

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 \(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:
ball Calendar (ICS file) download, for import into your favourite calendar application
ball UNCLUTTER for printing
ball AUTHENTICATE to mark the scnews item as read
School members may try to .