A topological approach to transductions

Jean-Éric Pin et Pedro V. Silva

PostScript file compressed with gzip, PDF file


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.

PostScript file compressed with gzip, PDF file


Valid HTML 4.01!