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 general 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 space/time 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1990
- Accession Number
- ADA223642
Entities
People
- J. Cai
- R. Paige
- R. Tarjan
Organizations
- Princeton University