×

Recognition of approximate occurrence of words on a Turing machine in real time. (Russian) Zbl 0553.68047

Let the alphabet \(\Sigma\) consist of quotients i/\(\nu\), where \(\nu\) is a natural number, i is an integer from the interval [-\(\nu\),\(\nu\) ], \(A=a_ 1,a_ 2,...,a_ r,\quad B=b_ 1,b_ 2,...,b_ r\) be two words over \(\Sigma\) of equal length. The distance between A and B depends on metrics defined on the set of all words over \(\Sigma\). The following metrics are considered: 1. Hamming metric \(l^ 0:\) \(\rho_ 0(A,B)=\sum^{r}_{j=1}sign| a_ j-b_ j|;\quad sign x=0\quad if\quad x=0,\quad 1\quad otherwise.\) 2. Metrics \(l^ n\); \(n=1,2,...:\quad \rho_ n(A,B)=(\sum^{r}_{j=1}| a_ j-b_ j|^ n)^{1/n}.\) 3. metric \(l^{\infty}:\) \(\rho_{\infty}(A,B)=\max_{1\leq j\leq r}| a_ j-b_ j|.\)
The words A, B are \(\epsilon\)-similar in a metric \(\mu\) if they are of equal length and \(\rho_{\mu}(A,B)\leq \epsilon\). The problem of recognition of approximate occurrence is: for fixed \(\epsilon\geq 0\) and two words V, U over \(\Sigma\) to determine, whether U contains a subword \(\epsilon\)-similar to v in the metric \(\mu\). The author considers the solution of the problem on multi-head Turing machines in real time in three different formulations depending on the way of representation of the input data. The main result is: for every \(\epsilon\geq 0\) and every metric \(l^ n\) (n\(\in N)\) there exists a Turing machine solving the problem in two formulations. As to the third formulation, there is no Turing machine solving it in real time. For the metric \(l^{\infty}\), effective algorithms were known earlier.
Reviewer: M.Kratko

MSC:

68Q45 Formal languages and automata
03D10 Turing machines and related notions
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite