Complexity and decidability results for some free inverse monoids
by
Volker Diekert
Universität Stuttgart, FMI
Coauthors: Markus Lohrey, Universität Stuttgart, Nicole Ondrusch, Universität Stuttgart

Margolis and Meakin have shown that the word problem for free inverse monoids modulo a finite idempotent presentation is decidable. Later another, more direct proof was given by da Silva. In the lecture we present a proof for this result using rewriting techniques over finite subsets of trees which leads to optimal algorithms for solving the word problem in the uniform and non-uniform setting.

Moreover, we show that the membership in rational subsets is decidable for these monoids. This implies that the generalized word problem is decidable, too. As matter of fact, our techniques can be extended to cope with virtually free groups as starting point. (This is interesting, for example because virtually free groups correspond exactly to the class of groups where the monadic second order logic of the Cayley graphs is decidable).

The results are closely related to the journal version for the MFCS 2005 contribution of Lohrey and Ondrusch.

Date received: March 13, 2006