RUS  ENG
Full version
JOURNALS // Chebyshevskii Sbornik // Archive

Chebyshevskii Sb., 2021 Volume 22, Issue 1, Pages 57–66 (Mi cheb986)

This article is cited 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)

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.

UDC: 519.115.8

Received: 12.12.2020
Accepted: 21.02.2021

DOI: 10.22405/2226-8383-2018-22-1-57-66



© Steklov Math. Inst. of RAS, 2024