This article is cited in 2 scientific papers (total in 2 papers)
Recognition of an approximate occurrence of words on a Turing machine in real time
A. G. Ivanov
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.
PDF file (5922 kB)
Mathematics of the USSR-Izvestiya, 1985, 24:3, 479–522
MSC: Primary 68C25; Secondary 68C40, 68G10
A. G. Ivanov, “Recognition of an approximate occurrence of words on a Turing machine in real time”, Izv. Akad. Nauk SSSR Ser. Mat., 48:3 (1984), 520–568; Math. USSR-Izv., 24:3 (1985), 479–522
Citation in format AMSBIB
\paper Recognition of an approximate occurrence of words on a~Turing machine in real time
\jour Izv. Akad. Nauk SSSR Ser. Mat.
\jour Math. USSR-Izv.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
Gad M. Landau, Uzi Vishkin, “Fast string matching with k differences”, Journal of Computer and System Sciences, 37:1 (1988), 63
P. A. Pevzner, M. S. Waterman, “Multiple filtration and approximate pattern matching”, Algorithmica, 13:1-2 (1995), 135
|Number of views:|