Geodesic
Recognition of an approximate occurrence of words on a Turing machine in real time
Izvestiya. Mathematics, Tome 24 (1985) no. 3, pp. 479-522 
A. G. Ivanov. Recognition of an approximate occurrence of words on a Turing machine in real time. Izvestiya. Mathematics, Tome 24 (1985) no. 3, pp. 479-522. http://geodesic.mathdoc.fr/item/IM2_1985_24_3_a2/
@article{IM2_1985_24_3_a2,
     author = {A. G. Ivanov},
     title = {Recognition of an approximate occurrence of words on {a~Turing} machine in real time},
     journal = {Izvestiya. Mathematics},
     pages = {479--522},
     year = {1985},
     volume = {24},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_1985_24_3_a2/}
}
TY  - JOUR
AU  - A. G. Ivanov
TI  - Recognition of an approximate occurrence of words on a Turing machine in real time
JO  - Izvestiya. Mathematics
PY  - 1985
SP  - 479
EP  - 522
VL  - 24
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/IM2_1985_24_3_a2/
LA  - en
ID  - IM2_1985_24_3_a2
ER  - 
%0 Journal Article
%A A. G. Ivanov
%T Recognition of an approximate occurrence of words on a Turing machine in real time
%J Izvestiya. Mathematics
%D 1985
%P 479-522
%V 24
%N 3
%U http://geodesic.mathdoc.fr/item/IM2_1985_24_3_a2/
%G en
%F IM2_1985_24_3_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

A Turing machine is constructed which in real time solves the problem of the approximate identification of occurrences of words with respect to a number of familiar metrics. This problem is a generalization of the well-known problem of detecting occurrences of words, and differs from the latter in that it is not the question of the occurrence of one word in another which is under investigation, but rather the question of the existence of some subword of the second word which differs from the first word by no more than a specified quantity, with respect to the metric under consideration. Bibliography: 9 titles.

[1] Slisenko A. O., “Slozhnostnye zadachi teorii vychislenii”, UMN, 36:6(222) (1981), 21–103 | MR | Zbl

[2] Matiyasevich Yu. V., “O raspoznavanii v realnoe vremya otnosheniya vkhozhdeniya”, Zap. nauchn. seminarov Leningr. otd. Matem. in-ta AN SSSR, 20, 1971, 104–114 | Zbl

[3] Adyan S. I., Problema Bernsaida i tozhdestva v gruppakh, Nauka, M., 1975 | MR | Zbl

[4] Freidzon R. I., “Ob odnoi kharakteristike slozhnosti rekursivnykh predikatov”, Trudy Matem. in-ta im. V. A. Steklova AN SSSR, 113, 1970, 79–101 | MR | Zbl

[5] Shtoss G. I., “$k$-lentochnoe modelirovanie $k$-golovochnoi mashiny Tyuringa”, Slozhnost vychislenii i algoritmov, Mir, M., 1974, 190–198

[6] Slisenko A. O., “Computational complexity of string and graph identification”, Lect. Notes Comput. Sci., 74, 1979, 182–190 | MR | Zbl

[7] Galil Z., “Real-time algorithms for string-matching and palindrome recognition”, 8th Annual ACM Symposium on theory of Computing, 1976, 161–173 | MR | Zbl

[8] Galil Z., Seiferos J., “Recognizing certain repetitions and reversals within strings”, 17th Annual Symposium on Foundation on Computer Science, 1976, 236–252 | MR

[9] Fisher M. J., Paterson M. S., “String-Matching and Other Products Complexity of Computation”, SIAM–AMS Proceedings, 7, 1974, 113–125 | MR