Compilation Techniques for Associative-Commutative Normalisation

Abstract

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.

Conference

Publication date: September 1997

Publication date (Print): September 1997

Pages: 1-12

Affiliations

LORIA & UHP

BP 101, 54602 Villers-les-Nancy CEDEX, FRANCE

http://www.loria.fr/equipes/protheo

LORIA & CNRS

BP 101, 54602 Villers-les-Nancy CEDEX, FRANCE

http://www.loria.fr/equipes/protheo

Article

DOI: 10.14236/ewic/AL1997.11

Copyright statement: © Pierre-Etienne Moreau et al. Published by BCS Learning and Development Ltd. Proceedings of the 2nd International Workshop on the Theory and Practice of Algebraic Specifications, Amsterdam

License:

This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Conference name: Proceedings of the 2nd International Workshop on the Theory and Practice of Algebraic Specifications

Conference acronym: AS

Conference number: 2

Conference location: Amsterdam

Conference date: 25-26 September 1997

Conference sponsor: Electronic Workshops in Computing (eWiC)

Conference theme: Theory and Practice of Algebraic Specifications

Product

Product Information: 1477-9358BCS Learning & Development

Self URI (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/AL1997.11

Self URI (journal page): https://ewic.bcs.org/

Categories

Series title: Electronic Workshops in Computing