This article is cited in 6 papers

Recognition of an approximate occurrence of words on a Turing machine in real time

A. G. Ivanov


Abstract: 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.

UDC: 510.6

MSC: Primary 68C25; Secondary 68C40, 68G10

Received: 22.03.1983

 English version: Mathematics of the USSR-Izvestiya, 1985, 24:3, 479–522

Bibliographic databases:

• 
•