H. Calbrix, THE 2ND-ORDER MONADIC THEORY OF THE FREE INVERSE MONOID IS UNDECIDABLE, Bulletin of the Belgian Mathematical Society Simon Stevin, 4(1), 1997, pp. 53-65
We solve in this paper the question of the decidability of the monadic
second order theory of the free inverse monoid. To this aim, we defin
e the notion of monadic second order theory of a given monoid, and the
combinatoric counterpart of this notion, the recognizable sets of gen
eralized words on a given monoid. Then we recall the definition of the
free inverse monoid and the characterization of this monoid that has
been given by Scheiblich. Using this characterisation and the Wang til
ing systems, Ne show that the second order theory of the free inverse
monoid on a singleton is undecidable, which entails the property for t
he free inverse monoid on a set which may contain more than one elemen
t.