Search

Nous r esolvons dans cet article la question de la d ecidabilit e de la th eorie monadique du second ordre du monode inversif libre. Nous d enissons a cette n la notion de th eorie monadique du second ordre d'un monode donn e et la contrepartie combinatoire de cette notion, les ensembles reconnaissables de mots g en eralis es sur un monode donn e. Nous rappelons alors la d enition du monode inversif libre ainsi que la caract erisation de ce monode due a Scheiblich. En utilisant cette caract erisation et les syst emes de pavages de Wang, nous montrons que la th eorie monadique du second ordre du monode inversif libre sur un singleton est ind ecidable, ce qui entra^ ne la propri et e pour le monode inversif libre sur un ensemble de plus d'un el ement. Abstract 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 dene the notion of monadic second order theory of a given monoid, and the combinat- oric counterpart of this notion, the recognizable sets of generalized words on a given monoid. Then we recall the denition of the free inverse monoid and the characterization of this monoid that has been given by Scheiblich. Using this characterisation and the Wang tiling systems, we show that the second order theory of the free inverse monoid on a singleton is undecidable, which entails the property for the free inverse monoid on a set which may contain more than one element.