Complexity measures of the words based on the string-matching and edit distance

Two variants $K_{A_1}(W)$ and $K_{A_2}(W)$ relative Kolmogorov's complexity of the words are considered. The measures are connected with the methods of compressed descriptions of the words: the definition of $K_{A_1}$ uses the instructions of the kind “repeat subword”, the definition of $K_{A_2}$ uses in addition to “repeat” the instructions “insert a letter”, “delete a letter”. The measure $K_{A_1}(W)$ can be evaluated in quadratic on $|W|$ time. One upper bound for $K_{A_2}$ computable in polynomial time is obtained. There were found some applications of $K_{A_1}$ in psychology.