Geodesic
Automaton mappings of words that propagate distortions in Hamming and Levenshteĭn metrics no more than $K$ times
Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 78-94 
A. V. Babash. Automaton mappings of words that propagate distortions in Hamming and Levenshteĭn metrics no more than $K$ times. Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 78-94. http://geodesic.mathdoc.fr/item/DM_2002_14_3_a8/
@article{DM_2002_14_3_a8,
     author = {A. V. Babash},
     title = {Automaton mappings of words that propagate distortions in {Hamming} and {Levenshte\u{i}n} metrics no more than $K$ times},
     journal = {Diskretnaya Matematika},
     pages = {78--94},
     year = {2002},
     volume = {14},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2002_14_3_a8/}
}
TY  - JOUR
AU  - A. V. Babash
TI  - Automaton mappings of words that propagate distortions in Hamming and Levenshteĭn metrics no more than $K$ times
JO  - Diskretnaya Matematika
PY  - 2002
SP  - 78
EP  - 94
VL  - 14
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2002_14_3_a8/
LA  - ru
ID  - DM_2002_14_3_a8
ER  - 
%0 Journal Article
%A A. V. Babash
%T Automaton mappings of words that propagate distortions in Hamming and Levenshteĭn metrics no more than $K$ times
%J Diskretnaya Matematika
%D 2002
%P 78-94
%V 14
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2002_14_3_a8/
%G ru
%F DM_2002_14_3_a8

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Babash A. V., Glukhov M. M., Shankin G. P., “O preobrazovaniyakh mnozhestva sloev v konechnom alfavite, ne razmnozhayuschikh iskazhenii”, Diskretnaya matematika, 9:3 (1997), 3–19 | MR | Zbl

[2] Glukhov M. M., “In'ektivnye otobrazheniya slov, ne razmnozhayuschie iskazhenii tipa propuska bukv”, Diskretnaya matematika, 11:2 (1999), 20–39 | MR | Zbl

[3] Levenshtein V. I., “O sovershennykh kodakh v metrike vypadenii i vstavok”, Diskretnaya matematika, 3:1 (1991), 3–20

[4] Glukhov M. M., “In'ektivnye otobrazheniya slov, ne razmnozhayuschie iskazhenii”, Matem. voprosy kibern., 7 (1998), 349–350 | MR

[5] Glukhov M. M., “In'ektivnye otobrazheniya slov, ne razmnozhayuschie iskazhenii”, Trudy po diskretnoi matematike, 4 (2001), 17–32