More efficient bottom-up multi-pattern matching in trees

J. Cai, R. Paige, R. Tarjan

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


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. A preliminary implementation of our algorithm runs ten times faster than Chase's (1987) implementation on the hardest problem instances. Our preprocessing algorithm has the advantage of being on-line with respect to pattern additions and deletions. It also adapts to favorable input instances, and on Hoffmann and O'Donnell's (1982) class of simple patterns, it performs better than their special-purpose algorithm tailored to this class. 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 (1982) simple patterns.

Original languageEnglish (US)
Pages (from-to)21-60
Number of pages40
JournalTheoretical Computer Science
Issue number1
StatePublished - Nov 30 1992

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'More efficient bottom-up multi-pattern matching in trees'. Together they form a unique fingerprint.

Cite this