Pure Maths Colloquium: Carl Frederick Nyberg-Brodda

The word problem for one-relation monoids has been called one of the most fundamental open problems in all combinatorial algebra. It has been open for over a century, and was described by P. S. Novikov as “containing something transcendental”. In this talk, I will give an overview of this problem (including all definitions!) and some important reduction results proved by S. I. Adian and his students. I will then focus on certain special classes, and show some recent results forming part of a program to understand the formal language theory of the word problem for one-relation monoids. This latter topic connects with the famous Muller-Schupp theorem, which identifies groups with context-free word problem as those which are virtually free. I will show that the Muller-Schupp theorem can be generalised to rather broad classes of one-relation monoids. As one consequence, I will show that it is decidable whether a one-relation monoid containing a non-trivial idempotent has context-free word problem. As another consequence, the difficult rational subset membership problem is solved for many classes of one-relation monoids.