Text size
  • Small
  • Medium
  • Large
  • Standard
  • Blue text on blue
  • High contrast (Yellow text on black)
  • Blue text on beige

    Compilation Techniques for Associative-Commutative Normalisation

    2nd International Workshop on the Theory and Practice of Algebraic Specifications

    Amsterdam, 25th - 26th September 1997


    P. E. Moreau & H. Kirchner


    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.


    PDF filePDF Version of this Paper (141kb)