@inproceedings{e084782e26454c9eb3e2759b1f1bec3a,
title = "More efficient bottom-up tree pattern matching",
abstract = "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{\textquoteright}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{\textquoteright}Donnell{\textquoteright}s Simple Patterns.",
author = "J. Cai and R. Paige and R. Tarjan",
year = "1990",
month = jan,
day = "1",
doi = "10.1007/3-540-52590-4_41",
language = "English (US)",
isbn = "9783540525905",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "72--86",
editor = "Andre Arnold",
booktitle = "CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings",
address = "Germany",
note = "15th Colloquium on Trees in Algebra and Programming, CAAP 1990 ; Conference date: 15-05-1990 Through 18-05-1990",
}