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

May 5, 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.