For a given set of n tuples, the binary consistency checking scheme generates a subset wherein no two elements intersect. The application of this scheme is illustrated by two problems in seismic horizon detection; seismic skeletonization and loop tying. After a brief introduction to seismic interpretation, these two examples are used to demonstrate how to cast an application problem into the formulism of the scheme. A comparison of this scheme to the dynamic programming approach to string matching due to S.Y. Lu (1982) is included.>

A quantitative criterion for measuring the effectiveness of the consensus obtained by pooling evidence from two knowledge sources is introduced. A brief review of the Dempster-Shafer theory of mathematical evidence, which is based on a set-theoretic description of subjective uncertainty, is given. The concept of generalized entropy as a measure of the uncertainty in a knowledge source is also introduced. It is proven that the pooling of evidence by Dempster's rule of combination decreases the total amount of generalized entropy in the knowledge sources. The decrease of entropy corresponds to the focusing of knowledge, and is used as a measure of consensus effectiveness. Several examples are used to illustrate this measure.>

A waveform correlation scheme is presented. The scheme consists of four parts: 1) the representation of waveforms by trees, 2) the definition of basic operations on tree nodes and tree distance, 3) a tree matching algorithm, and 4) a backtracking procedure to find the best node-to-node correlation. This correlation scheme has been implemented. Results show that the scheme has the capability of handling distortions that result from stretching or shrinking of intervals or from missing intervals.

The syntax errors on trees are defined in terms of five types of error transformations, namely, substitution, stretch, split, branch, and deletion. The distance between two trees is the least cost sequence of error transformations needed to transform one to the other. Based on this definition, a class of error-correcting tree automata (ECTA) is proposed. The operation of ECTA is illustrated by a character recognition example.

Cluster analysis for patterns represented by sentences is investigated. The similarity between patterns is expressed in terms of the distance between their corresponding sentences. A weighted distance between two strings is defined and its probabilistic interpretation given. The class membership of an input pattern (sentence) is determined according to the nearest neighbor or k-nearest neighbor rule. A clustering procedure on a sentence-to-sentence basis is proposed. A set of English characters is used to illustrate the proposed metric and clustering procedure.

In this paper, a probabilistic model for error-correcting parsing with substitution, insertion, and deletion errors is introduced. The formulation of maximum-likelihood error-correcting parser (MLECP) by incorporating the noise model into stochastic grammars is also presented. The use of stochastic error-correcting parsers for recognition of noisy and/or distorted patterns results in a process of high accuracy, but with low efficiency. In order to make the syntax analysis more practically feasible, it is proposed to use a sequential classification method for noisy strings processing. Computation results based on the classification experiments of noisy patterns for both nonsequential and sequential error-correcting parsers are presented.

A distance between two syntactic patterns is defined in terms of error transformations. This definition is extended to the case of distance measures between one syntactic pattern and a group of syntactic patterns. A nearest neighbor recognition rule for syntactic patterns using the proposed distance is then given. Using the proposed distance as a similarity measure, a clustering procedure for syntactic patterns is described. A character recognition experiment is given as an illustrative example.