SEMINAR: Mathematics & Statistics Colloquium: Solving equations in free groups.
|Mathematics & Statistics Colloquium: Solving equations in free groups.
Colloquium time date and location: 4pm, Thursday 21st May, Blakers
Speaker: Dr. Murray Elder, University of Newcastle
Title. Solving equations in free groups.
An equation in a free group is an expression U=V where U,V are words over elements of the group and variables X,Y,Z, etc. A solution is an assignment of group elements to the variables which make the equation true.
In the 1970s, Makanin constructed a (really complicated) algorithm which decides if an equation has a solution or not. Later, Razborov extended Makanin's result to find all solutions. The complexity of these algorithms was subsequently shown to be pretty bad.
In this talk I will present a new approach, describing a finite graph that encodes all solutions in reduced words, which has exponential size and can be constructed in nondeterministic quasilinear space (in the length of the equation). I will try to motivate and explain the problem, how it relates to some questions in logic, and give some of the ingredients of the proof.
Dr. Murray Elder
Blakers Lecture Theatre
Thu, 21 May 2015 16:00
Thu, 21 May 2015 17:00
Luke Morgan <[email protected]>
Tue, 12 May 2015 09:22
- Locations of venues on the Crawley and Nedlands campuses are
available via the Campus Maps website.
- Download this event as:
Mail this event: