BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:Semigroups with low difficulty word problem - Mark
us Pfeiffer\, St Andrew's
DTSTART;TZID=Europe/London:20130422T160000
DTEND;TZID=Europe/London:20130422T170000
UID:TALK44947AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/44947
DESCRIPTION:The word problem for groups is a well-studied noti
on in\ncomputational group theory. Results of Anis
imov\, Muller and Schupp\, Lehnert\nand Schweitzer
\, Holt\, Roever\, Thomas and many more relate the
word problem and\nthe coword problem of (classes
of) groups to (classes of) formal languages\,\nfor
example regular languages and context-free langua
ges.\nIn my research I considered a natural defini
tion of the word problem and the\ncoword problem o
f semigroups.\nUsing the notions of recognisable\,
rational\, and extended rational subsets of\nmono
ids\, I extended some of the results about groups
to semigroups.\nI then defined a hierarchy of semi
groups by difficulty of their word\nproblem.\n\nIn
my talk I will give an accessible overview of the
results\, and I will show\nhow my results can be
seen in the context of logic and complexity theory
.\nI will also give a few open questions which I h
ope to answer in the near\nfuture.
LOCATION:Room TBC. Microsoft Research\, Station Road
CONTACT:Jonathan Hayman
END:VEVENT
END:VCALENDAR