TY - GEN
T1 - More efficient bottom-up tree pattern matching
AU - Cai, J.
AU - Paige, R.
AU - Tarjan, R.
N1 - Funding Information:
1. Part of this work was done while Paige was a summer faculty at IBM T, J. watson Research Center. This work is also partly based on research suptx~ed by the Office of Naval Research under Contract No. N00014-8%0461. 2. Research at Prlnceson University partially supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, grant NSF-STC88-09648, and the Office of Naval Research, contract N00014-S7-K-0467.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1990.
PY - 1990
Y1 - 1990
N2 - Pattern matching in trees is fundamental to a variety of programming language systems. However, progress has been slow in satisfying a pressing need for genera] purpose pattern matching algorithms that are efficient in both time and space. We offer asymptotic improvements in both time and space to Chase’s bottom-up algorithm for pattern preprocessing. Our preprocessing algorithm has the additional advantage of being incremental with respect to pattern additions and deletions. We show how to modify our algorithm using a new decomposition method to obtain a spaceAime tradeoff. Finally, we trade a log factor in time for a linear space bottom-up pattern matching algorithm that handles a wide subclass of Hoffmann and O’Donnell’s Simple Patterns.
AB - Pattern matching in trees is fundamental to a variety of programming language systems. However, progress has been slow in satisfying a pressing need for genera] purpose pattern matching algorithms that are efficient in both time and space. We offer asymptotic improvements in both time and space to Chase’s bottom-up algorithm for pattern preprocessing. Our preprocessing algorithm has the additional advantage of being incremental with respect to pattern additions and deletions. We show how to modify our algorithm using a new decomposition method to obtain a spaceAime tradeoff. Finally, we trade a log factor in time for a linear space bottom-up pattern matching algorithm that handles a wide subclass of Hoffmann and O’Donnell’s Simple Patterns.
UR - http://www.scopus.com/inward/record.url?scp=85027613477&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027613477&partnerID=8YFLogxK
U2 - 10.1007/3-540-52590-4_41
DO - 10.1007/3-540-52590-4_41
M3 - Conference contribution
AN - SCOPUS:85027613477
SN - 9783540525905
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 72
EP - 86
BT - CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings
A2 - Arnold, Andre
PB - Springer Verlag
T2 - 15th Colloquium on Trees in Algebra and Programming, CAAP 1990
Y2 - 15 May 1990 through 18 May 1990
ER -