Algebra and Logic Seminar - 7/1/2015

Wednesday, 7 January 2015, 2:00 p.m.

Lecturer: Robert Gray (East Anglia University, UK)

Title: "The word problem for semigroups generated by idempotents"

Local: Room 1.13, Edifício VII
Faculdade de Ciências e Tecnologia, Quinta da Torre, Caparica

Abstract: A group or semigroup S defined by a set of generators X and a set of defining relations R (i.e. defined by a presentation) is said to have decidable word problem if there exists an algorithm which, for any pair of words over the alphabet, decides whether they represent the same element of S. It is well known that, even if a group or semigroup is given by a finite presentation, the word problem may be undecidable. Given this, over the years quite a lot of work in this area has been done on identifying and studying classes of finitely presented groups and semigroups where the word problem is decidable (e.g. hyperbolic groups, automatic semigroups and groups). After giving some history and background on the word problem in general, I will go on to speak about some recent joint work with Igor Dolinka (Novi Sad) and Nik Ruskuc (St Andrews) investigating the word problem for a particular class of finitely presented semigroups, called free idempotent generated semigroups. I will say something about why people are interested in these semigroups, and explain how the groups that they embed can be used to obtain results (both positive and negative) about the word problem for semigroups in this class.