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

      0 references
      1984
      0 references
      distance of words
      0 references
      Hamming metric
      0 references
      recognition of approximate occurrence
      0 references
      multi-head Turing machines
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references