Transduction rationnelle
En informatique théorique, en linguistique, en théorie des automates et en théorie des langages, une transduction rationnelle est une transformation de mots et de langages définie par un transducteur fini ou au moyen d'une relation rationnelle. Une relation rationnelle fonctionnelle est aussi appelé fonction rationnelle.

Les transductions rationnelles ont été introduites et étudiées par C. C. Elgot et J. E. Mezei, par Marcel-Paul Schützenberger et Maurice Nivat, et employées notamment par Seymour Ginsburg et Sheila Greibach dans l'étude des langages algébriques.

Définition 

Une relation rationnelle sur deux alphabets  et  est une partie rationnelle du monoïde produit . En d'autres termes, c'est un élément de la plus petite famille de parties de  contenant la relation vide, les singletons, et fermées par union, produit, et l'opération étoile, c'est-à-dire passage au sous-monoïde engendré.
 Le produit de deux éléments  et  de  est le couple , le produit de deux parties  et  de  est l'ensemble de 
 L' étoile d'une partie  de  est la partie , où  est le produit de  facteurs égaux à .

Une transduction rationnelle de  vers  est une application de  dans l'ensemble des parties de  dont le graphe est une relation rationnelle. Plus formellement,  est une transduction rationnelle si  est une relation rationnelle; réciproquement, si  est une relation rationnelle, la transduction de  vers  définie par  est une transduction rationnelle.

Certaines propriétés s'expriment plus simplement en termes de relation rationnelle, d'autre en termes de transduction rationnelle.

Transduction et transducteur 

La fonction réalisée par un transducteur fini est une transduction rationnelle. Réciproquement, pour toute transduction rationnelle, il existe un transducteur fini qui la réalise.

Propriétés 

 Composition Si  et  sont des transductions rationnelles, la transduction composée  définie par  est une transduction rationnelle.
 InverseSi  est une transduction rationnelle, la transduction inverse  définie par  est rationnelle.
 Représentation par morphisme Pour toute transduction rationnelle , il existe un alphabet , deux morphismes  et  et un langage rationnel  tels que  pour tout .
 Préservation de la rationalité et de l’algébricité L'image d'un langage rationnel (resp. d'un langage algébrique) par une transduction rationnelle est un langage rationnel (resp.un langage algébrique).

Exemples de transductions rationnelles 
 Un morphisme est une transduction rationnelle
 Un morphisme inverse est une transduction rationnelle
 L'intersection avec un langage rationnel est une transduction rationnelle
 La transduction qui, à un mot de , associe l'ensemble de ses préfixes, resp. suffixes, facteurs, sous-mots, est une transduction rationnelle.

Cône rationnel 
Un cône rationnel, est une famille de langages fermée par transduction rationnelle. D'après la propriété de représentation, il est équivalent de demander qu'une famille de langages est fermée par morphisme, morphisme inverse et intersection avec un langage rationnel.

Un cône rationnel est appelé full trio en anglais. La raison est qu'un cône est fermé par un « trio » d'opérations et que le morphisme peut être effaçant, ce que les américains notent par l'adjectif full.

Un cône fidèle est une famille de langages fermée par morphisme non effaçant, morphisme inverse et intersection avec un langage rationnel. C'est ce qui est appelé trio en anglais. 

Les langages rationnels, les langages algébriques, mais aussi de nombres sous-familles des langages algébriques, comme les langages linéaires, les langages à un compteur, les langages quasi-rationnels forment des cônes rationnels. Les langages context-sensitifs forment un cône fidèle.

Un cône rationnel est principal s'il existe un langage (un générateur) tel que tout langage du cône est image de ce générateur par une transduction rationnelle. Le théorème de Chomsky-Schützenberger dit, dans une version un peu renforcée, que le cône des langages algébriques est principal, et que tout langage de Dyck sur au moins deux paires de parenthèses en est un générateur.

Notes

Références

Liens internes 
 Automate fini
 Langage rationnel
 Ensemble rationnel
 Théorie des automates
 Demi-groupe automatique

Théorie des automates
Langage formel
Calculabilité
Méthode formelle