More efficient bottom-up tree pattern matching

J. Cai, R. Paige, R. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 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 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.

Original languageEnglish (US)
Title of host publicationCAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings
EditorsAndre Arnold
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783540525905
StatePublished - 1990
Event15th Colloquium on Trees in Algebra and Programming, CAAP 1990 - Copenhagen, Denmark
Duration: May 15 1990May 18 1990

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume431 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other15th Colloquium on Trees in Algebra and Programming, CAAP 1990

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this