SEMINAR:
Mathematics & Statistics Colloquium: Solving equations in free groups.
Thu, 21 May 2015 16:00 - Blakers Lecture Theatre
Dr. Murray Elder
Colloquium time date and location: 4pm, Thursday 21st May, Blakers
Lecture Theatre.
Speaker: Dr. Murray Elder, University of Newcastle
Title. Solving equations in free groups.
Abstract. 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.
For more information:
Luke Morgan
luke.morgan@uwa.edu.au
Starts : Thu, 21 May 2015 16:00
Ends : Thu, 21 May 2015 17:00
Last Updated : Tue, 12 May 2015 09:22