Let FIM(X) be the free inverse monoid on a finite set X. The word problem of FIM(X) is easily seen to be recognisable in linear space (e.g. using Munn trees), and this has been improved to log space (Lohrey and Ondrusch 2007).

In this talk I will consider the complexity of the word problem of FIM(X) from a language theory perspective.  It is context-sensitive (equivalent to linear-space), but not context-free.  There is a rich world of interesting language classes in between the context-free and context-sensitive, and I will discuss where the word problem of FIM(X) fits within that world.  This is work in progress.