by Olivier Carton and Wolfgang Thomas
Nous considérons la structure (N,<,P) des entiers naturels munis de l'ordre, étendue par un prédicat unaire P. Nous montrons que pour un prédicat morphique P, la théorie monadique du second ordre associée MTh(N,<,P) est décidable. Ce résultat étend les résultats précédents de Elgot et Rabin (1966) et Maes (1999). La solution est obtenue par des méthodes de théorie des semigroupes, qui sont reliées à l'approche par automates de Elgot et Rabin. Finalement, nous montrons comment ces méthodes permettent d'obtenir une large classe de prédicats P pour lesquels la théorie MTh(N,<,P) est décidable.
We present new examples of infinite words which have a decidable monadic theory. Formally, we consider structures (N,<,P) which expand the ordering (N,<) of the natural numbers by a unary predicate P; the corresponding infinite word is the characteristic 0-1-sequence xP of P. We show that for a morphic predicate P the associated monadic second-order theory MTh(N,<,P) is decidable, thus extending results of Elgot and Rabin (1966) and Maes (1999). The solution is obtained in the framework of semigroup theory, which is then connected to the known automata theoretic approach of Elgot and Rabin. Finally, a large class of predicates P is exhibited such that the monadic theory MTh(N,<,P) is decidable, which unifies and extends the previously known examples.
PostScript Files