The Dehn function for a semigroup or group $M$ is an asymptotic measure of how bad the "naive solution" to the word problem in $M$ may be. The word problem in $M$ is decidable if and only if the Dehn function of $M$ is a recursive function, but frequently the Dehn function is significantly more poorly behaved than the complexity of the word problem. On the other hand, the word problem for one-relation monoids is one of the most intriguing and important open problems in semigroup theory. For that reason, it makes sense to ask: how bad can the Dehn function of a one-relation monoid be? I will present the history of the problem, as well as some of my own recent progress on this topic for the class of one-relation monoids where the relation is of the form $bUa = a$, for a word $U$, answering in particular a question posed by Cain $\&$ Maltcev in 2013.

Start Date

Venue

Online Zoom meeting

End Date

Carl-Fredrik Nyberg brodda

Université Gustave Eiffel (Paris, France)

Semigroups, Automata and Languages