SEMINAR: Groups and Combinatorics Seminar: Solving equations in free groups and free monoids with constraints
|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.
Fri, 22 May 2015 15:00
Fri, 22 May 2015 16:00
Gabriel Verret <[email protected]>
Tue, 19 May 2015 09:15
- Locations of venues on the Crawley and Nedlands campuses are
available via the Campus Maps website.
- Download this event as:
Mail this event: