Geodesic
On the possibility of a periodic word reconstruction from the subwords of fixed length
Čebyševskij sbornik, Tome 22 (2021) no. 1, pp. 57-66.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{CHEB_2021_22_1_a3,
     author = {V. A. Alekseev and Y. G. Smetanin},
     title = {On the possibility of a periodic word reconstruction from the subwords of fixed length},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {57--66},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2021_22_1_a3/}
}
TY  - JOUR
AU  - V. A. Alekseev
AU  - Y. G. Smetanin
TI  - On the possibility of a periodic word reconstruction from the subwords of fixed length
JO  - Čebyševskij sbornik
PY  - 2021
SP  - 57
EP  - 66
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2021_22_1_a3/
LA  - ru
ID  - CHEB_2021_22_1_a3
ER  - 
%0 Journal Article
%A V. A. Alekseev
%A Y. G. Smetanin
%T On the possibility of a periodic word reconstruction from the subwords of fixed length
%J Čebyševskij sbornik
%D 2021
%P 57-66
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2021_22_1_a3/
%G ru
%F CHEB_2021_22_1_a3
V. A. Alekseev; Y. G. Smetanin. On the possibility of a periodic word reconstruction from the subwords of fixed length. Čebyševskij sbornik, Tome 22 (2021) no. 1, pp. 57-66. http://geodesic.mathdoc.fr/item/CHEB_2021_22_1_a3/

[1] Leontev V. K., Smetanin Yu. G., “O vosstanovlenii vektorov po naboru ikh fragmentov”, Doklady Akademii nauk, 302:6 (1988), 1319–1322 | Zbl

[2] Manvel B. et al., “Reconstruction of sequences”, Discrete Mathematics, 94:3 (1991), 209–219 | DOI | MR | Zbl

[3] Skiena S. S., Sundaram G., “Reconstructing strings from substrings”, Journal of Computational Biology, 2:2 (1995), 333–353 | DOI | MR

[4] Leontev V. K., “Zadachi vosstanovleniya slov po fragmentam i ikh prilozheniya”, Diskretnyi analiz i issledovanie operatsii, 2:2 (1995), 26–48 | MR

[5] Gusfield D., “Algorithms on stings, trees, and sequences: Computer science and computational biology”, Acm Sigact News, 28:4 (1997), 41–60 | DOI | MR

[6] Krasikov I., Roditty Y., “On a reconstruction problem for sequences”, Journal of combinatorial theory, Series A, 77:2 (1997), 344–348 | DOI | MR | Zbl

[7] Scott A. D., “Reconstructing sequences”, Discrete Mathematics, 175:1-3 (1997), 231–238 | DOI | MR | Zbl

[8] Borwein P., Erdélyi T., Kós G., “Littlewood-type problems on [0, 1]”, Proceedings of the London Mathematical Society, 79:1 (1999), 22–46 | DOI | MR | Zbl

[9] Levenshtein V. I., “Efficient reconstruction of sequences from their subsequences or supersequences”, Journal of Combinatorial Theory, Series A, 93:2 (2001), 310–332 | DOI | MR | Zbl

[10] Dud{\i}k M., Schulman L. J., “Reconstruction from subsequences”, Journal of Combinatorial Theory, Series A, 103:2 (2003), 337–348 | DOI | MR | Zbl

[11] Batu T. et al., Reconstructing strings from random traces, Departmental Papers (CIS), 2004, 173 pp. | MR

[12] Kannan S., McGregor A., “More on reconstructing strings from random traces: insertions and deletions”, Proceedings International Symposium on Information Theory, ISIT 2005, IEEE, 2005, 297–301

[13] Lin J. et al., “Experiencing SAX: a novel symbolic representation of time series”, Data Mining and knowledge discovery, 15:2 (2007), 107–144 | DOI | MR

[14] Smetanin Y., Ul'yanov M., Determining the characteristics of Kolmogorov complexity of time series: an approach based on symbolic descriptions, 2013