UWA Logo What's On at UWA
   UWA HomeProspective Students  | Current Students  | Staff  | Alumni  | Visitors  | About  |     Search UWA    for      
 

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

* Login to add events... *
Today's date is Saturday, November 28, 2020
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:
Additional Information:
  • 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:

Top of Page
© 2001-2010  The University of Western Australia
Questions? Mail [email protected]