La décision du problème de compléments AC, à partir d'un terme T et d'un ensemble de termes S1, Sn, consiste à vérifier s'il existe une AC-instance close de t qui ne soit couverte par aucune des AC-instances closes des termes S1,, Sn. Nous décrivons deux approches du problème: l'une de type descendante utilisant le principe des arbres de motifs introduit par e. Kounalis, l'autre de type ascendante, s'appuyant sur la réalisation d'automates ascendant d'arbres avec conditions ayant de bonnes propriétés. La décision du problème de compléments AC général reste néanmoins un problème ouvert et les deux méthodes présentées permettent de décider d'un certain nombre de cas non-linéaires ou en particulier les termes du problème peuvent avoir des occurrences multiples de variables que sous un même symbole de fonction (AC ou non). Des extensions du problème à d'autres théories (AC1, ACI) sont possibles ainsi que la décision de problèmes similaires tels que la propriété de réductibilité inductive modulo AC