RUS  ENG
Full version
JOURNALS // Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia // Archive

Dokl. RAN. Math. Inf. Proc. Upr., 2022 Volume 503, Pages 16–22 (Mi danma241)

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.

UDC: 519.115.8

Presented: K. V. Rudakov
Received: 23.03.2021
Revised: 27.01.2022
Accepted: 17.02.2022

DOI: 10.31857/S2686954322020035


 English version:
Doklady Mathematics, 2022, 105:2, 61–67

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024