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

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


Diskretnaya Matematika, 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 Bqn 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 B2n and the set of permutations Sn (SnBnn) 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 Bqn 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 Bqn with correction of individual deletions as q/n.
Received: 28.12.1989
Bibliographic databases:
UDC: 519.72, 519.1
Language: Russian
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://mathscinet.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:
  • https://www.mathnet.ru/eng/dm771
  • https://www.mathnet.ru/eng/dm/v3/i1/p3
  • This publication is cited in the following 3 articles:
    1. 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
    2. 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
    3. 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
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Statistics & downloads:
    Abstract page:913
    Full-text PDF :430
    References:1
    First page:1
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025