More efficient bottom-up tree pattern matching

J. Cai, R. Paige, R. Tarjan

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

7 Scopus citations

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’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
Pages72-86
Number of pages15
ISBN (Print)9783540525905
DOIs
StatePublished - Jan 1 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

Other

Other15th Colloquium on Trees in Algebra and Programming, CAAP 1990
CountryDenmark
CityCopenhagen
Period5/15/905/18/90

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Cai, J., Paige, R., & Tarjan, R. (1990). More efficient bottom-up tree pattern matching. In A. Arnold (Ed.), CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings (pp. 72-86). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 431 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-52590-4_41