Abstract
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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
J. Christian. Fast Knuth-Bendix completion: Summary. In RTA'89, pages 551–555. Springer-Verlag LNCS 355, 1989.
D. Kapur D. Benanav and P. Narendran. Complexity of matching problems. Journal of Symbolic Computation, 3:203–216, 1987.
N. Dershowitz and J.-P. Jouannaud. Rewrite systems. In Handbook of Theoretical Computer Science, volume B, chapter 6, pages 243–309. Elsevier, 1990.
A. Graf. Left-to-right tree pattern matching. In RTA '91, pages 323–334. Springer-Verlag LNCS 488, 1991.
J.-M. Hullot. A catalogue of canonical term rewriting systems. Technical Report CSL-113, SRI International, April 1980.
E. Kounalis and D. Lugiez. Compilation of pattern matching with associativecommutative functions. In TAPSOFT'91, pages 57–73. Springer-Verlag LNCS 493, 1991.
D. Lugiez and J.L. Moysset. Complement problems and tree automata in AC-like theories. To appear in STACS'93.
W. McCune. Experiments with discrimination-tree indexing and path indexing for term retrieval. Technical Report MCS-P191-1190, Argonne National Laboratory, Argonne, Illinois, USA, January 1991.
D. Nicolaita. An indexing scheme for AC-equational theories. Technical report, Research Institute for Infomatics, Bucharest, Romania, February 1992.
R. Ramesh, I.V. Ramakrishnan, and D.S. Warren. Automata-driven indexing of prolog clauses. In Seventh Annual ACM Symposium on Principles of Programming Languages, pages 281–290, San Francisco, 1990.
R.C. Sekar, R. Ramesh, and I.V. Ramakrishnan. Adaptive pattern matching. In ICALP'92, pages 247–260. Springer-Verlag LNCS 623, 1992.
M. E. Stickel. The path-indexing method for indexing terms. Technical Report 473, SRI International, Menlo Park, California, USA, October 1989.
R. M. Verma and I.V. Ramakrishnan. Tight complexity bounds for term matching problems. Information and Computation, 101(1):33–69, November 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bachmair, L., Chen, T., Ramakrishnan, I.V. (1993). Associative-commutative discrimination nets. In: Gaudel, M.C., Jouannaud, J.P. (eds) TAPSOFT'93: Theory and Practice of Software Development. CAAP 1993. Lecture Notes in Computer Science, vol 668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56610-4_56
Download citation
DOI: https://doi.org/10.1007/3-540-56610-4_56
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56610-6
Online ISBN: 978-3-540-47598-9
eBook Packages: Springer Book Archive