Complexity measures of the words based on the string-matching and edit distance
Zapiski Nauchnykh Seminarov POMI, Theoretical application of methods of mathematical logic. Part III, Tome 105 (1981), pp. 18-23
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{ZNSL_1981_105_a3,
author = {A. N. Grigor'eva},
title = {Complexity measures of the words based on the string-matching and edit distance},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {18--23},
publisher = {mathdoc},
volume = {105},
year = {1981},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_1981_105_a3/}
}
A. N. Grigor'eva. Complexity measures of the words based on the string-matching and edit distance. Zapiski Nauchnykh Seminarov POMI, Theoretical application of methods of mathematical logic. Part III, Tome 105 (1981), pp. 18-23. http://geodesic.mathdoc.fr/item/ZNSL_1981_105_a3/