SEMINAR: Mathematics & Statistics Colloquium: Solving equations in free groups.


Mathematics & Statistics Colloquium: Solving equations in free groups. 
Other events...

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.
Speaker(s) 
Dr. Murray Elder

Location 
Blakers Lecture Theatre


Contact 
Luke Morgan
<[email protected]>

Start 
Thu, 21 May 2015 16:00

End 
Thu, 21 May 2015 17:00

Submitted by 
Luke Morgan <[email protected]>

Last Updated 
Tue, 12 May 2015 09:22

Included in the following Calendars: 

 Locations of venues on the Crawley and Nedlands campuses are
available via the Campus Maps website.
 Download this event as:
Text 
iCalendar

Mail this event:
