Résumé : Cet article est une contribution aux
fondations mathématiques de la théorie des automates. Nous
donnons une caractérisation topologique des transductions
τ d'un monoïde M dans un monoïde N,
telles que si R est un langage reconnaissable de N,
τ-1(R) est un langage reconnaissable de M. Nous
imposons deux conditions sur les monoïdes, qui sont satisfaites dans
tous les cas d'intérêt pratique: les monoïdes doivent
être résiduellement finis et, pour chaque entier positif
n, il doit exister un nombre fini de congruences d'indice n.
Notre solution procède en deux étapes. Nous montrons tout
d'abord qu'un tel monoïde, équipé de la distance de
Hall, est un espace métrique dont la complétion est compacte.
Nous prouvons ensuite que τ peut être étendu en une
application τ^ de M dans l'ensemble des parties compactes
de la complétion de N. Ce dernier ensemble, muni de la
métrique de Hausdorff, est de nouveau un monoïde compact.
Finalement, notre résultat principal montre que
τ-1 préserve les ensembles reconnaissables si
et seulement si τ^ est continu.
Abstract : This paper is a contribution to the mathematical
foundations of the theory of automata. We give a topological
characterization of the transductions τ from a monoid M
into a monoid N, such that if R is a recognizable subset of
N, τ-1(R) is a recognizable subset of M.
We impose two conditions on the monoids, which are fullfilled in all cases
of practical interest: the monoids must be residually finite and, for every
positive integer n, must have only finitely many congruences of
index n. Our solution proceeds in two steps. First we show that such
a monoid, equipped with the so-called Hall distance, is a metric space
whose completion is compact. Next we prove that τ can be lifted
to a map τ^ from M into the set of compact subsets of the
completion of N. This latter set, equipped with the Hausdorff
metric, is again a compact monoid. Finally, our main result states that
τ-1 preserves recognizable sets if and only if
τ^ is continuous.