Abstract

The word problem for groups is a well-studied notion in computational group theory. Results of Anisimov, Muller and Schupp, Lehnert and Schweitzer, Holt, Roever, Thomas and many more relate the word problem and the coword problem of (classes of) groups to (classes of) formal languages, for example regular languages and context-free languages. In my research I considered a natural definition of the word problem and the coword problem of semigroups. Using the notions of recognisable, rational, and extended rational subsets of monoids, I extended some of the results about groups to semigroups. I then defined a hierarchy of semigroups by difficulty of their word problem.

In my talk I will give an accessible overview of the results, and I will show how my results can be seen in the context of logic and complexity theory. I will also give a few open questions which I hope to answer in the near future.