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.
UDC:
519.115.8
Presented:K. V. Rudakov Received: 23.03.2021 Revised: 27.01.2022 Accepted: 17.02.2022