|
MATHEMATICS
On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length
V. A. Alekseeva, Yu. G. Smetaninb a Moscow Institute of Physics and Technology (National Research University), Dolgoprudnyi, Moscow oblast, Russia
b Federal Research Center "Computer Science and Control",'' Russian Academy of Sciences, Moscow, Russia
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.
Citation:
V. A. Alekseev, Yu. G. Smetanin, “On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length”, Dokl. RAN. Math. Inf. Proc. Upr., 503 (2022), 16–22; Dokl. Math., 105:2 (2022), 61–67
Linking options:
https://www.mathnet.ru/eng/danma241 https://www.mathnet.ru/eng/danma/v503/p16
|
|