THE 2ND-ORDER MONADIC THEORY OF THE FREE INVERSE MONOID IS UNDECIDABLE

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.