BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Semigroups with low difficulty word problem - Markus Pfeiffer\, St
  Andrew's
DTSTART:20130422T150000Z
DTEND:20130422T160000Z
UID:TALK44947@talks.cam.ac.uk
CONTACT:Jonathan Hayman
DESCRIPTION:The word problem for groups is a well-studied notion in\ncompu
 tational group theory. Results of Anisimov\, Muller and Schupp\, Lehnert\n
 and Schweitzer\, Holt\, Roever\, Thomas and many more relate the word prob
 lem and\nthe coword problem of (classes of) groups to (classes of) formal 
 languages\,\nfor example regular languages and context-free languages.\nIn
  my research I considered a natural definition of the word problem and the
 \ncoword problem of semigroups.\nUsing the notions of recognisable\, ratio
 nal\, and extended rational subsets of\nmonoids\, I extended some of the r
 esults about groups to semigroups.\nI then defined a hierarchy of semigrou
 ps by difficulty of their word\nproblem.\n\nIn my talk I will give an acce
 ssible overview of the results\, and I will show\nhow my results can be se
 en in the context of logic and complexity theory.\nI will also give a few 
 open questions which I hope to answer in the near\nfuture.
LOCATION:Room TBC.  Microsoft Research\, Station Road
END:VEVENT
END:VCALENDAR