RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskr. Mat., 1991, Volume 3, Issue 1, Pages 3–20 (Mi dm771)  

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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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:
    1. 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  mathnet  crossref  mathscinet  zmath
    2. Glukhov M.M., “Injective mappings of words which do not multiply symbol skip and insertion errors”, Probabilistic Methods in Discrete Mathematics, 2002, 1–7  isi
    3. B. A. Pogorelov, M. A. Pudovkina, “Naturalnye metriki i ikh svoistva. Ch. 1. Podmetriki i nadmetriki”, Matem. vopr. kriptogr., 2:4 (2011), 49–74  mathnet  crossref
  • Дискретная математика
    Number of views:
    This page:512
    Full text:252
    First page:1

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019