New algorithm for linear tree pattern matching

Abstract

Tree pattern matching is foundational to a wide variety of applications in Computer Science. We consider the problem of linear tree pattern matching and adopt a technique used for parsing context-free languages for this purpose. We exploit the fact that a skeletal parse tree (the subject tree itself) is already available, and view the problem as one of tiling this tree in all possible ways, using productions representing input patterns. Our technique works in a bottom-up fashion, and requires matching time linear in the size of the tree. It offers potential advantages over existing bottom-up techniques in terms of auxiliary space required during pattern matching. We have tested the technique on several input data sets and report the results in this thesis.