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

V. A. Alekseev ; Y. G. Smetanin

Čebyševskij sbornik, Tome 22 (2021) no. 1, pp. 57-66

Résumé

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)$.

Détail

Keywords: word reconstruction, multiset of subwords, subwords of fixed length, periodic word.