Paper Info
Title
A Compiler for Rewrite Programs in Associative-Commutative Theories
Abstract
We address 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 match- ing method is based on the construction of compact bipartite graphs, and is designed for working very efficiently on specific classes of ACpatterns. We show how to refine this algorithm to work in an eager way. General patterns are handled through a program transformation process. Variable instantia- tion resulting from the matching phase and construction of the resulting term are also addressed. Our experimental results with the system ELAN provide strong evidence that compilation of many-to-one AC normalisation using the combination of these few techniques is crucial for improving the performance of algebraic programming languages.
Year
DOI
Venue
1998
10.1007/BFb0056617
PLILP/ALP
Keywords
Field
DocType
ac many-to-one matching.,ac theories,associative-commutative theories,rewrite systems,compilation,rewrite programs,programming language,bipartite graph
Graph theory,Discrete mathematics,Program transformation,Programming language,Formal language,Commutative property,Modulo,Computer science,Bipartite graph,Compiler,Rewriting
Conference
ISBN
Citations 
PageRank 
3-540-65012-1
22
1.68
References 
Authors
20
2
Name
Order
Citations
PageRank
Pierre-etienne Moreau159840.40
Hélène Kirchner21655152.66