TY - GEN
T1 - Associative-commutative discrimination nets
AU - Bachmair, Leo
AU - Chen, Ta
AU - Ramakrishnan, I. V.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.
PY - 1993
Y1 - 1993
N2 - Use of discrimination nets for many-to-one pattern matching has been shown to dramatically improve the performance of the Knuth-Bendix completion procedure used in rewriting. Many important applications of rewriting require associative-commutative (AC) function symbols and it is therefore quite natural to expect performance gains by using similar techniques for AC-completion. In this paper we propose such a technique, called AC-discrimination net, that is a natural generalization of the standard discrimination net in the sense that if no AC-symbols are present in the pattern, it specializes to the standard discrimination net. Moreover we show how AC-discrimination nets can be augmented so as to further improve the performance of AC-matching on problems that are typically seen in practice.
AB - Use of discrimination nets for many-to-one pattern matching has been shown to dramatically improve the performance of the Knuth-Bendix completion procedure used in rewriting. Many important applications of rewriting require associative-commutative (AC) function symbols and it is therefore quite natural to expect performance gains by using similar techniques for AC-completion. In this paper we propose such a technique, called AC-discrimination net, that is a natural generalization of the standard discrimination net in the sense that if no AC-symbols are present in the pattern, it specializes to the standard discrimination net. Moreover we show how AC-discrimination nets can be augmented so as to further improve the performance of AC-matching on problems that are typically seen in practice.
UR - https://www.scopus.com/pages/publications/0002034059
U2 - 10.1007/3-540-56610-4_56
DO - 10.1007/3-540-56610-4_56
M3 - Conference contribution
AN - SCOPUS:0002034059
SN - 9783540566106
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 61
EP - 74
BT - TAPSOFT 1993
A2 - Gaudel, Marie-Claude
A2 - Jouannaud, Jean-Pierre
PB - Springer Verlag
T2 - 4th International Joint Conference on the Theory and Practice of Software Development, TAPSOFT 1993
Y2 - 13 April 1993 through 17 April 1993
ER -