SEMINAR: Groups and Combinatorics Seminar: Solving equations in free groups and free monoids with constraints

Time and place: 15:00 Friday 22 May in Weatherburn LT.

Speaker: Murray Elder (University of Newcastle)

Title: Solving equations in free groups and free monoids with constraints.

Abstract: My talk will give some details of the proof of our result - that the set of all solutions to an equation over a free group or free monoid has a simple description encoded by a finite graph, that can be constructed in space O(n log n).

- reduction from an equation over a free group to an equation over a free monoid with involution with constraints

- extended equations and partial commutation

- construction of the finite graph encoding all solutions

- two propositions: any path in the graph from an initial to final vertex is a solution; and any solution is realised by a finite path in the graph from an initial to final vertex

- algorithm to prove the second proposition - block and pair compression. This is joint work with Laura Ciobanu, Neuchatel and Volker Diekert, Stuttgart.