TY - GEN
T1 - More efficient bottom-up tree pattern matching
AU - Cai, J.
AU - Paige, R.
AU - Tarjan, R.
N1 - 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 -