| Abstrakt: | Lot of research was done on the string similarity, due to many practical applications (similarities of DNA/RNA structures, etc). In the first part of this work, we shall introduce an abstract model of the distance of words, from which the known distances such as edit-distance (Levenshtein distance) can be derived. We shall present some other instances of this model. We shall discuss what derivations can/cannot be effectively computed. In the second part of this work we shall extend the notion of the distance on words to the distance of a word and a language. We present algorithm for computing $\Delta$-similarity of a word and a context-free language.
|
|---|