La structure des expressions arithmétiques étudiées peut présenter
une mise en forme "préalable" qui empêcherait toute optimisation
ultérieure. Il est donc nécessaire dans un premier temps de
"normaliser" les expressions. Dans le même temps, nous tenterons de
"nettoyer" les expressions en leur appliquant diverses simplifications
algébriques élémentaires (a+0=a, , etc...). Ces
transformations font appel à des règles de réécriture (techniques de
pattern-matching) et la prise en compte du caractère associatif,
commutatif, ou autre, des opérateurs rend le problème difficile
(NP-complet).
S'il existe des algorithmes efficaces de pattern-matching associatif commutatif, nous n'avons pu trouver d'outil intégrant des notions qui nous seraient utiles telles que: