Grammaire à substitution d’arbre de complexité polynomiale : un cadre efficace pour DOP-

Trouver l’arbre d’analyse le plus probable dans le cadre du modèle DOP (Data-Oriented Parsing) _une version probabiliste de grammaire à substitution d’arbres développée par R. Bod (1992) _ est connu pour être un problème NP-difficile dans le cas le plus général (Sima’an, 1996a). Cependant, si l’on introduit des restrictions a priori sur le choix des arbres élémentaires, on peut obtenir des instances particulières de DOP pour lesquelles la recherche de l’arbre d’analyse le plus probable peut être effectuée en un temps polynomial (par rapport à la taille de la phrase à analyser). La présente contribution se propose d’étudier une telle instance polynomiale de DOP, fondée sur le principe de sélection miminale-maximale et d’en évaluer les performances sur deux corpus différents.