A SYSTEM FOR APPROXIMATE TREE MATCHING

Ordered, labeled trees are trees in which each node has a label and th e left-to-right order of its children (if it has any) is fixed. Such t rees have manv applications in vision, pattern recognition, molecular biology, programming compilation, and natural language processing. Man y or the applications involve comparing trees or retrieving/extracting information from a repository of trees. Examples include classificati on of unknown patterns. analysis of newly sequenced RNA structures, se mantic taxonomy for dictionary definitions, generation of interpreters for nonprocedural programming languages, and automatic error recovery and correction for programming languages. Previous systems use exact matching (or generalized regular expression matching) for tree compari son. This paper presents a system, called Approximate-Tree-By-Example (ATBE), which allows inexact matching of trees. The ATBE system intera cts with the user through a simple but powerful query language; graphi cal devices are provided to facilitate inputing the queries. The paper describes the architecture of ATBE, illustrates its use and describes some aspects of ATBE implementation. We also discuss the underlying a lgorithms and provide some sample applications.