No label defined (Q3216153)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3881896
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3881896 |
Statements
1984
0 references
distance of words
0 references
Hamming metric
0 references
recognition of approximate occurrence
0 references
multi-head Turing machines
0 references
0.7662413716316223
0 references
0.7614238262176514
0 references
0.7503869533538818
0 references
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.
0 references