Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia
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



Dokl. RAN. Math. Inf. Proc. Upr.:
Year:
Volume:
Issue:
Page:
Find






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


Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia, 2022, Volume 503, Pages 16–22
DOI: https://doi.org/10.31857/S2686954322020035
(Mi danma241)
 

MATHEMATICS

On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length

V. A. Alekseeva, Yu. G. Smetaninb

a Moscow Institute of Physics and Technology (National Research University), Dolgoprudnyi, Moscow oblast, Russia
b Federal Research Center "Computer Science and Control",'' Russian Academy of Sciences, Moscow, Russia
References:
Abstract: We consider the problem of reconstructing a word from a multiset of its fragments of fixed length. Words consist of symbols from a finite alphabet. The word to be reconstructed is assumed to be periodic or contain a periodic word as a subword. It is shown that a periodic word with a period $p$ can be reconstructed from a multiset of its fragments of length $k$, where $k\geq\left \lfloor{\frac{16}7\sqrt{p}}\right \rfloor+5$. For a word consisting of a $q$-periodic prefix repeated $m$ times and a $p$-periodic suffix repeated $l$ times, if $l\geq mq^{\left \lfloor{\frac{16}7\sqrt{P}}\right \rfloor+5}$, then the estimate becomes $k\geq\left \lfloor{\frac{16}7\sqrt{P}}\right \rfloor+5$, where $P=\max(p,q)$.
Keywords: word, fragment, subword, periodic word, reconstruction from incomplete information, word reconstruction, multiset of subwords.
Funding agency Grant number
Russian Foundation for Basic Research 19-07-00150
This work was supported by the Russian Foundation for Basic Research, project no. 19-07-00150.
Presented: K. V. Rudakov
Received: 23.03.2021
Revised: 27.01.2022
Accepted: 17.02.2022
English version:
Doklady Mathematics, 2022, Volume 105, Issue 2, Pages 61–67
DOI: https://doi.org/10.1134/S106456242202003X
Bibliographic databases:
Document Type: Article
UDC: 519.115.8
Language: Russian
Citation: V. A. Alekseev, Yu. G. Smetanin, “On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length”, Dokl. RAN. Math. Inf. Proc. Upr., 503 (2022), 16–22; Dokl. Math., 105:2 (2022), 61–67
Citation in format AMSBIB
\Bibitem{AleSme22}
\by V.~A.~Alekseev, Yu.~G.~Smetanin
\paper On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length
\jour Dokl. RAN. Math. Inf. Proc. Upr.
\yr 2022
\vol 503
\pages 16--22
\mathnet{http://mi.mathnet.ru/danma241}
\crossref{https://doi.org/10.31857/S2686954322020035}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4448467}
\elib{https://elibrary.ru/item.asp?id=48506195}
\transl
\jour Dokl. Math.
\yr 2022
\vol 105
\issue 2
\pages 61--67
\crossref{https://doi.org/10.1134/S106456242202003X}
Linking options:
  • https://www.mathnet.ru/eng/danma241
  • https://www.mathnet.ru/eng/danma/v503/p16
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024