|
This article is cited in 3 scientific papers (total in 3 papers)
Perfect codes in the metric of deletions and insertions
V. I. Levenshtein
Abstract:
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$.
Full text:
PDF file (2177 kB)
English version:
Discrete Mathematics and Applications, 1992, 2:3, 241–258
Bibliographic databases:
UDC:
519.72, 519.1 Received: 28.12.1989
Citation:
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
\Bibitem{Lev91}
\by V.~I.~Levenshtein
\paper Perfect codes in the metric of deletions and insertions
\jour Diskr. Mat.
\yr 1991
\vol 3
\issue 1
\pages 3--20
\mathnet{http://mi.mathnet.ru/dm771}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1112284}
\zmath{https://zbmath.org/?q=an:0787.94023|0732.94015}
\transl
\jour Discrete Math. Appl.
\yr 1992
\vol 2
\issue 3
\pages 241--258
Linking options:
http://mi.mathnet.ru/eng/dm771 http://mi.mathnet.ru/eng/dm/v3/i1/p3
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
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: |
This page: | 567 | Full text: | 295 | First page: | 1 |
|