Résumé : Nous donnons une présentation
unifiée pour traiter le problème suivant. Soient
(L1, ..., Ln) → f(L1, ...,
Ln) une opération sur les langages. Etant
donné des monoïdes reconnaissant les langages
L1, ..., Ln, donner une construction
explicite d'un monoïde reconnaissant f(L1, ...,
Ln). Notre méthode donne en particulier une
façon simple de s'assurer qu'une opération préserve
les langages rationnels. La portée de notre méthode est
très large et va d'opérations classiques telles que union,
intersection, concaténation, quotient, mélange, morphismes et
inverses de morphisme, etc. à d'autres moins classiques comme
l'infiltration, la réduction de Dyck, le plus long préfixe
commun, le comptage de Straubing, etc. Il comprend également des
questions qui ne s'expriment pas directement comme opération sur les
langages, telles que, par exemple, le théorème de Reutenauer
sur les TOL-systèmes. L'idée clé de notre construction
est de considérer une opération comme l'inverse d'une
transduction.
Abstract : We give a unified framework to treat the following
problem. Let (L1, ..., Ln) → f(L1,
..., Ln) be an operation on languages. Given monoids
recognizing the languages L1, ..., Ln, give an
explicit construction of a monoid recognizing f(L1, ...,
Ln). Our method gives in particular a simple way to prove
that an operation preserves rational languages. The scope of our
method is quite broad and goes from classical operations such as union,
intersection, concatenation, quotient, shuffle, inverse and direct
morphisms, etc., to less classical ones such as infiltration, Dyck
reduction, longest common prefix, Straubing's counting, etc. It includes
also questions that are not expressed directly as operations on languages,
as, for example, Reutenauer's theorem on TOL-systems. The key idea of our
construction is to consider an operation as the inverse of a transduction.