|
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)
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.
Received: 12.12.2020 Accepted: 21.02.2021
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
Linking options:
https://www.mathnet.ru/eng/cheb986 https://www.mathnet.ru/eng/cheb/v22/i1/p57
|
|