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^[1], 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[modifier | modifier le code]

Une relation rationnelle sur deux alphabets $A$ et $B$ est une partie rationnelle du monoïde produit $A^{*}\times B^{*}$ . En d'autres termes, c'est un élément de la plus petite famille de parties de $A^{*}\times B^{*}$ 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 $(x,y)$ et $(x',y')$ de $A^{*}\times B^{*}$ est le couple $(xx',yy')$ , le produit de deux parties $R$ et $R'$ de $A^{*}\times B^{*}$ est l'ensemble de $RR'=\{rr'\mid r\in R,r'\in R'\}$
L' étoile d'une partie $R$ de $A^{*}\times B^{*}$ est la partie $R^{*}=\cup _{n\geq 0}R^{n}$ , où $R^{n}$ est le produit de $n$ facteurs égaux à $R$ .

Une transduction rationnelle de $A^{*}$ vers $B^{*}$ est une application de $A^{*}$ dans l'ensemble des parties de $B^{*}$ dont le graphe est une relation rationnelle^[2]. Plus formellement, $f:A^{*}\to B^{*}$ est une transduction rationnelle si $\{(x,y)\mid y\in f(x)\}$ est une relation rationnelle; réciproquement, si $R\subset A^{*}\times B^{*}$ est une relation rationnelle, la transduction de $A^{*}$ vers $B^{*}$ définie par $x\mapsto \{y\in B^{*}\mid (x,y)\in R\}$ 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[modifier | modifier le code]

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[modifier | modifier le code]

Composition: Si $f:A^{*}\to B^{*}$ et $g:B^{*}\to C^{*}$ sont des transductions rationnelles, la transduction composée $h:A^{*}\to C^{*}$ définie par $h(x)=\{z\in C^{*}\mid \exists y\in B^{*}:y\in f(x){\text{ et }}z\in g(y)\}$ est une transduction rationnelle.
Inverse: Si $f:A^{*}\to B^{*}$ est une transduction rationnelle, la transduction inverse $f^{-1}:B^{*}\to A^{*}$ définie par $x\in f^{-1}(y)\iff y\in f(x)$ est rationnelle.
Représentation par morphisme: Pour toute transduction rationnelle $f:A^{*}\to B^{*}$ , il existe un alphabet $C$ , deux morphismes $\alpha :C^{*}\to A^{*}$ et $\beta :C^{*}\to B^{*}$ et un langage rationnel $K\subset C^{*}$ tels que $f(x)=\beta (\alpha ^{-1}(x)\cap K)$ pour tout $x\in A^{*}$ .
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[modifier | modifier le code]

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 $x$ , associe l'ensemble de ses préfixes, resp. suffixes, facteurs, sous-mots, est une transduction rationnelle.

Cône rationnel[modifier | modifier le code]

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[modifier | modifier le code]

↑ Elgot et Mezei (1965)
↑ Il y a là un abus de notation: on écrit $f:A^{*}\to B^{*}$ alors que l'on devrait écrire $f:A^{*}\to {\mathfrak {P}}(B^{*})$

Références[modifier | modifier le code]

Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5)
Traduction anglaise avec corrections: Elements of Automata Theory, Cambridge University Press 2009, (ISBN 9780521844253)

Jean-Michel Autebert et Luc Boasson, Transductions rationnelles : Application aux Langages Algébriques, Masson, 1988 (ISBN 978-2-225-81504-1)

(en) Calvin C. Elgot et Jorge E. Mezei, « On relations defined by generalized finite automata », IBM J. Res. and Develop., vol. 9,‎ 1965, p. 47-68 (DOI 10.1147/rd.91.0047)

(en) Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, 313 p. (ISBN 0-7204-2506-9)

(en) Jean Berstel et Luc Boasson, « Context-free Languages », dans Jan van Leeuwen (éditeur), Handbook of Theoretical Computer Science, vol. B : Formal Models and Semantics, Elsevier, 1990 (ISBN 978-0444880741), p. 59-102

Liens internes[modifier | modifier le code]

Portail de l'informatique théorique

[1] Elgot et Mezei (1965)

[2] Il y a là un abus de notation: on écrit $f:A^{*}\to B^{*}$ alors que l'on devrait écrire $f:A^{*}\to {\mathfrak {P}}(B^{*})$

[1]

[2]

v · m Informatique théorique
Codage	Codage de l'information Compression de données Chiffrement Cryptanalyse Cryptographie Théorie de l'information
Modèles de calcul	Calculabilité Décidabilité et indécidabilité Ensemble récursif Problème de l'arrêt Ensemble récursivement énumérable Machine de Turing Thèse de Church Automate cellulaire Réseau de neurones artificiels Réduction polynomiale Problème NP-complet Principe de Church-Turing-Deutsch
Algorithmique	Algorithmique Algorithme glouton Algorithme probabiliste Algorithme génétique Complexité algorithmique Analyse d'algorithme Diviser pour régner Heuristique Programmation dynamique Géométrie algorithmique Algorithmes de tri Algorithmique du texte Exploration de données Science des données Apprentissage profond Test de primalité Structure de données Arbre enraciné Concurrence Parallélisme
Syntaxe	Réécriture Compilation Expression régulière Grammaire formelle Langage rationnel Ensemble rationnel Théorie des langages Théorie des automates Automate fini Automate sur les mots infinis Automate d'arbres Automate à pile Hiérarchie de Chomsky Linguistique informatique
Sémantique	Interprétation abstraite Méthodes formelles Vérification de modèles Sémantique des langages de programmation Sémantique dénotationnelle Sémantique axiomatique Sémantique opérationnelle
Logique mathématique	Assistant de preuve Calcul des prédicats Correspondance de Curry-Howard Fonction récursive Lambda-calcul Théorèmes d'incomplétude de Gödel Théorie des types
Mathématiques discrètes	Combinatoire Algorithme du simplexe Optimisation combinatoire Théorie des graphes Algorithmes de la théorie des graphes Recherche opérationnelle Théorie de la décision Analyse numérique