This article is cited in 3 scientific papers (total in 3 papers)
Perfect codes in the metric of deletions and insertions
V. I. Levenshtein
We consider a problem of packing and covering a metric space $B^n_q$ that consists of $q$-ary words of length $n$ and is provided with a metric of deletions and insertions. For any $n=1,2,…$ we present partitions of the space $B^n_2$ and the set of permutations $S_n$ $(S_n\subset B^n_n)$ into perfect codes with correction of individual deletions. In connection with a problem of constructing ordered codes with correction of $s$ deletions we formulate a problem of constructing ordered Steiner systems and give a solution of this problem for certain values of the parameters. We construct codes complete in $B^n_q$ with correction of individual deletions for $n=3$ and any $q$, and also for $n=4$ and any even $q$. We find the asymptotic behavior of the maximum cardinality of the code in $B^n_q$ with correction of individual deletions as $q/n\to\infty$.
PDF file (2177 kB)
Discrete Mathematics and Applications, 1992, 2:3, 241–258
V. I. Levenshtein, “Perfect codes in the metric of deletions and insertions”, Diskr. Mat., 3:1 (1991), 3–20; Discrete Math. Appl., 2:3 (1992), 241–258
Citation in format AMSBIB
\paper Perfect codes in the metric of deletions and insertions
\jour Diskr. Mat.
\jour Discrete Math. Appl.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
A. V. Babash, “Automaton mappings of words that propagate distortions in Hamming and Levenshteĭn metrics no more than $K$ times”, Discrete Math. Appl., 12:4 (2002), 375–392
Glukhov M.M., “Injective mappings of words which do not multiply symbol skip and insertion errors”, Probabilistic Methods in Discrete Mathematics, 2002, 1–7
B. A. Pogorelov, M. A. Pudovkina, “Naturalnye metriki i ikh svoistva. Ch. 1. Podmetriki i nadmetriki”, Matem. vopr. kriptogr., 2:4 (2011), 49–74
|Number of views:|