Error-Correcting Syntax Analysis for Tree Languages.

摘要

An error-correcting version of tree automation is studied. Assume the syntax errors on trees to be of five types: substitution, stretch, split, branch, and deletion. The error-correction problem is to determine the distance between two trees as measured by the minimum cost sequence of error transformations needed to transform one to the other. Two types of error-correcting tree automation (ECTA) are proposed: structure-preserved ECTA and generalized ECTA. The structure-preserved ECTA takes substitution errors into consideration only. A LANDSAT data interpretation problem is used as an example to illustrate the process of structure-preserved ECTA. The restriction on tree structure is removed in formulating the generalized ECTA. All five types of syntax errors are considered. Any erroneous tree, in this case, is able to find its most similar (in terms of minimum distance) correction in the sense of both node-labeling and tree structure. (Author)