A String Correction Method Based on the Context-Dependent Similarity

Primitive sequences of patterns, phoneme sequences and spellings are essentially context-dependent. This paper describes the string-tostring correction problem based on the context-dependent edit operations. The edit operations investigated allow substituting symbols of a string into another symbols, deleting symbols from a string, and inserting symbols into a string whose costs determined depending on their contexts. The invariance of the similarity to parallel transformations, a separation theorem and topological equivalence are described.