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 $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,\dots $ 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$.
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:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Statistics & downloads:
    Abstract page:821
    Full-text PDF :393
    First page:1
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024