Procédure de décision pour la vitesse de croissance des Macro Transducteurs d’Arbre

5 mai 2025

Charles Peyrat (LACL)

Les Macro Transducteurs d’Arbre (ou MTT) sont un modèle de fonctions entre langages d’arbre qui généralise les transducteurs d’arbre top-down classiques. Ils furent introduits en 1980 pour étudier les grammaires à attributs, un modèle utilisé en traitement du langage naturel et en compilation pour assigner une sémantique aux mots d’un langage context-free. Nous présenterons ici, après avoir introduits les modèles en question, une classe spéciale de MTTs dite « depth-proper », toute aussi expressive que les MTT classique, et dans laquelle il est possible de décider si la fonction réalisée a une croissance linéaire en hauteur (LHI) ou non.