Error-Correcting Syntax Analysis for Tree Languages.

Abstract

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1976
Accession Number
ADA032744

Entities

People

  • King Sun Fu
  • S. Y. Lu

Organizations

  • Purdue University

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies
  • Space

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Automata Theory
  • Character Recognition
  • Computer Graphics
  • Computers
  • Electrical Engineering
  • Engineering
  • Feature Extraction
  • Image Processing
  • Language
  • Pattern Recognition
  • Probabilistic Models
  • Probability
  • Probability Distributions
  • Recognition
  • Trees (Data Structures)

Readers

  • Computer Programming and Software Development.
  • Computer Science.
  • Operations Research