Résumé : Deux résultats de
Schützenberger (1965) et McNaughton et Papert (1971) permettent
d'évaluer avec précision le pouvoir expressif des structures
ordonnées colorées. Dans cet article, nous étudions le
pouvoir expressif des formules existentielles et des combinaisons
booléennes des formules existentielles dans une logique enrichie par
les prédicats numériques modulaires. Nous donnons d'abord une
description combinatoire des langages reconnaissables définissables
par ces deux fragments de la logique du premier ordre, puis nous en donnons
une caractérisation en termes de morphismes syntactiques. Il en
résulte que l'on peut effectivement décider si un langage
reconnaissable donné est capturé par l'un de ses fragments.
Les preuves reposent sur des techniques non triviales de théorie des
semigroupes: timbres, catégories dérivées et produits
en couronne.
Abstract : Two results by Schützenberger (1965)
and by McNaughton and Papert (1971) lead to a precise description of the
expressive power of first order logic on words interpreted as ordered
colored structures. In this paper, we study the expressive power of
existential formulas and of Boolean combinations of existential formulas in
a logic enriched by modular numerical predicates. We first give a
combinatorial description of the corresponding regular languages, and then
give an algebraic characterization in terms of their syntactic morphisms.
It follows that one can effectively decide whether a given regular language
is captured by one these two fragments of first order logic. The proofs
rely on nontrivial techniques of semigroup theory: stamps, derived
categories and wreath products.