Résumé : Le but de cet article est de présenter
deux outils algébriques (les transductions représentables et
les morphismes relationnels) qui ont été utilisés dans
la décennie précédente pour étudier les
opérations sur les langages reconnaissables. Cette étude
réserve quelques surprises. En effet, les deux concepts ont
été introduits à l'origine pour d'autres raisons: les
transductions représentables sont une formalisation des automates
avec sortie et ont été principalement étudiées
en liaison ave la théorie des langages algébriques, alors que
les morphismes relationnels ont été introduits par Tilson
pour résoudre des problèmes liés ) la
décomposition en produit en couronne des semigroupes finis. Mais il
apparait que les morphismes relationnels constituent un outil très
puissant dans l'étude des langages reconnaissables et que les
transductions conduisent à de jolis problèmes de
théorie des semigroupes.
La théorie des variétés d'Eilenberg fournit une
correspondance biunivoque entre les variétés de semigroupes
et les variétés de langages. Une partie des résultats
présentés dans cet article montrents que, dans certains cas,
cette correspondance peut être étendue aux opérations.
En d'autres termes, une opération sur les langages (telle que la
concaténation, les morphismes préservant la longueur, etc.)
est en correspondance avec une opération sur les semigroupes. Il est
alors tentant de demander si les opérations les plus naturelles sur
les langages (respectivement semigroupes) ont une contrepartie naturelle en
terms de semigroupes (respectivement langages). Cela conduit à de
nombreux problèmes difficiles, dont certains ne sont pas encore
résolus.
Abstract : The aim of the article is to present two algebraic tools
(the representable transductions and the relational morphisms) that have
been used in the past decade to study operations on recognizable languages.
This study reserves a few surprises. Indeed, both concepts were originally
introduced for other purposes: representable transductions are a
formalization of automata with output and have been mainly studied in
connection with the theory of context-free languages, while relational
morphisms were introduced by Tilson to solve some problems related to the
wreath product decomposition of finite semigroups. But it turns out that
relational morphisms are a very powerful tool in the study of recognizable
languages and that transductions lead to some very nice problems on finite
semigroups.
Eilenberg's variety theorem gives a one-to-one correspondence between
varieties of semigroups and varieties of languages. Part of the results
reviewed in this article show that, in certain cases, this correspondence
can be extended to operations. That is, an operation on languages (such as
concatenation, length-preserving morphism, etc.) is in correspondence with
an operation on semigroups. It is therefore tempting to ask whether the
most natural operations on languages (respectively semigroups) have a
natural counterpart in terms of semigroups (respectively languages). This
leads to a number of difficult problems, some of which are still unsolved.