zbMATH — the first resource for mathematics

More efficient bottom-up tree pattern matching. (English) Zbl 0759.68030
CAAP’90, Proc. 15th Colloq., Copenhagen/Denmark 1990, Lect. Notes Comput. Sci. 431, 72-86 (1990).
Summary: [For the entire collection see Zbl 0745.00027.]
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 D. Chase’s [An improvement to bottom-up tree pattern matching in Proc. Fourteenth Annual ACM Symposium on Principles of Programming Languages, 168-177 (1987)] 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 Ch. M. Hoffmann and M. J. O’Donnell’s [J. Assoc. Comput. Mech. 29, 68-95 (1982; Zbl 0477.68067); ACM Trans. Program. Lang. Syst. 4, 83-112 (1982; Zbl 0481.68008)] simple patterns.

68Q25 Analysis of algorithms and problem complexity
68W10 Parallel algorithms in computer science
68N15 Theory of programming languages