Compilation Techniques for Associative-Commutative Normalisation
Pierre‐Etienne Moreau, Claude Kirchner · Electronic workshops in computing · 1997
We consider the problem of term normalisation modulo associative-commutative (AC) theories and describe several techniques for compiling many-to-one AC matching and reduced term construction. The proposed method, illustrated on three examples, is based on compact bipartite graphs, and is designed for working very efficiently on specific classes of AC patterns. Our experimental results provide strong evidence that compilation of many-to-one AC normalisation is a useful technique for improving the performance of algebraic programming languages.