|
Automaton mappings of words that propagate distortions in Hamming and Levenshteĭn metrics no more than $K$ times
A. V. Babash
Abstract:
Let $I$ and $O$ be finite alphabets. For a finite alphabet $\Omega$, let $\Omega^*$ denote the set of all words of finite lengths over the alphabet $\Omega$. In this paper we give a complete description of all automaton mappings of the set $I^*$ into $O^*$ which multiply symbol replacement errors in words by a factor not exceeding $K$. We give a complete description of injective automaton mappings of the set $I^*$ into $O^*$ which multiply symbol skip errors by a factor no greater than $K$. A similar result is obtained for the deletion and insertion metric.
Received: 18.09.2001
Citation:
A. V. Babash, “Automaton mappings of words that propagate distortions in Hamming and Levenshteĭn metrics no more than $K$ times”, Diskr. Mat., 14:3 (2002), 78–94; Discrete Math. Appl., 12:4 (2002), 375–392
Linking options:
https://www.mathnet.ru/eng/dm256https://doi.org/10.4213/dm256 https://www.mathnet.ru/eng/dm/v14/i3/p78
|
| Statistics & downloads: |
| Abstract page: | 502 | | Full-text PDF : | 323 | | References: | 57 | | First page: | 1 |
|