Chebyshevskii Sbornik
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Chebyshevskii Sb.:
Year:
Volume:
Issue:
Page:
Find






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


Chebyshevskii Sbornik, 2021, Volume 22, Issue 1, Pages 57–66
DOI: https://doi.org/10.22405/2226-8383-2018-22-1-57-66
(Mi cheb986)
 

This article is cited in 1 scientific paper (total in 1 paper)

On the possibility of a periodic word reconstruction from the subwords of fixed length

V. A. Alekseeva, Y. G. Smetaninb

a Moscow Institute of Physics and Technology (MIPT) (Moscow)
b Federal Research Center «Computer Science and Control», Russian Academy of Sciences (Moscow)
Full-text PDF (705 kB) Citations (1)
References:
Abstract: The problem being considered is the reconstruction of periodic words from a finite alphabet using multiset of fixed length subwords. This is a special case of a more general problem of reconstruction with incomplete information and under restrictions on the words in question. For some constraints on the multiset of subwords, conditions for possibility of reconstruction are obtained. It is shown that a periodic word with period $p$ is uniquely determined by the multiset of its subwords of length $k \geq \left\lfloor\frac{16}{7} \sqrt{p}\right\rfloor + 5$. For a word consisting of a non-periodic prefix of length $q$ and a periodic suffix with period $p$, repeated $l$ times, a similar estimate is obtained: $k \geq \left\lfloor\frac{16}{7} \sqrt{P}\right\rfloor + 5$, provided $l \geq q^{\left\lfloor\tfrac{16}{7} \sqrt{P}\right\rfloor + 5}$ where $P = \max(p, q)$.
Keywords: word reconstruction, multiset of subwords, subwords of fixed length, periodic word.
Funding agency Grant number
Russian Foundation for Basic Research 19-07-00150
Received: 12.12.2020
Accepted: 21.02.2021
Document Type: Article
UDC: 519.115.8
Language: Russian
Citation: V. A. Alekseev, Y. G. Smetanin, “On the possibility of a periodic word reconstruction from the subwords of fixed length”, Chebyshevskii Sb., 22:1 (2021), 57–66
Citation in format AMSBIB
\Bibitem{AleSme21}
\by V.~A.~Alekseev, Y.~G.~Smetanin
\paper On the possibility of a periodic word reconstruction from the subwords of fixed length
\jour Chebyshevskii Sb.
\yr 2021
\vol 22
\issue 1
\pages 57--66
\mathnet{http://mi.mathnet.ru/cheb986}
\crossref{https://doi.org/10.22405/2226-8383-2018-22-1-57-66}
Linking options:
  • https://www.mathnet.ru/eng/cheb986
  • https://www.mathnet.ru/eng/cheb/v22/i1/p57
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024