Preview

Чебышевский сборник

Расширенный поиск

О возможности восстановления периодического слова по подсловам фиксированной длины

https://doi.org/10.22405/2226-8383-2021-22-1-57-66

Полный текст:

Аннотация

Рассмотрена задача реконструкции слов из конечного алфавита по частичной информации при дополнительных ограничениях на допустимые слова.
А именно, ставится задача о восстановлении периодического слова по мультимножеству его подслов одной длины.
Для некоторых видов частичной информации и ограничений получены условия однозначной реконструкции.
Показано, что периодическое слово с периодом $$p$$ однозначно определяется мультимножеством его подпоследовательностей длины $$k \geq \left\lfloor\frac{16}{7} \sqrt{p}\right\rfloor + 5$$.
Для слова, состоящего из непериодического префикса длины $$q$$ и периодического суффикса с периодом $$p$$, повторяющегося $$l$$ раз, получена аналогичная оценка $$k \geq \left\lfloor\frac{16}{7} \sqrt{P}\right\rfloor + 5$$ при условии $$l \geq q^{\left\lfloor\tfrac{16}{7} \sqrt{P}\right\rfloor + 5}$$, где $$P = \max(p, q)$$.

Об авторах

Василий Антонович Алексеев
Московский физико-технический институт (национальный исследовательский университет)
Россия

ассистент кафедры информатики и вычислительной математики, ассистент кафедры высшей математики



Юрий Геннадьевич Сметанин
Федеральный исследовательский центр «Информатика и управление» Российской академии наук
Россия

доктор физико-математических наук, главный научный сотрудник



Список литературы

1. Леонтьев В. К., Сметанин Ю.Г. О восстановлении векторов по набору их фрагментов //Доклады Академии наук. – Российская академия наук, 1988. – Т. 302. – №. 6. – С. 1319-

2.

3. Manvel B. et al. Reconstruction of sequences //Discrete Mathematics. – 1991. – Т. 94. – №. 3. – С. 209-219.

4. Skiena S. S., Sundaram G. Reconstructing strings from substrings //Journal of Computational Biology. – 1995. – Т. 2. – №. 2. – С. 333-353.

5. Леонтьев В. К. Задачи восстановления слов по фрагментам и их приложения //Дискретный анализ и исследование операций. – 1995. – Т. 2. – №. 2. – С. 26-48.

6. Gusfield D. Algorithms on stings, trees, and sequences: Computer science and computational biology //Acm Sigact News. – 1997. – Т. 28. – №. 4. – С. 41-60.

7. Krasikov I., Roditty Y. On a reconstruction problem for sequences //journal of combinatorial theory, Series A. – 1997. – Т. 77. – №. 2. – С. 344-348.

8. Scott A. D. Reconstructing sequences //Discrete Mathematics. – 1997. – Т. 175. – №. 1-3. – С. 231-238.

9. Borwein P., Erd´elyi T., K´os G. Littlewood-type problems on [0, 1] //Proceedings of the London Mathematical Society. – 1999. – Т. 79. – №. 1. – С. 22-46.

10. Levenshtein V. I. Efficient reconstruction of sequences from their subsequences or supersequences //Journal of Combinatorial Theory, Series A. – 2001. – Т. 93. – №. 2. – С. 310-332.

11. Dudık M., Schulman L. J. Reconstruction from subsequences //Journal of Combinatorial Theory, Series A. – 2003. – Т. 103. – №. 2. – С. 337-348.

12. Batu T. et al. Reconstructing strings from random traces //Departmental Papers (CIS). – 2004. – С. 173.

13. Kannan S., McGregor A. More on reconstructing strings from random traces: insertions and deletions //Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. – IEEE, 2005. – С. 297-301.

14. Lin J. et al. Experiencing SAX: a novel symbolic representation of time series //Data Mining and knowledge discovery. – 2007. – Т. 15. – №. 2. – С. 107-144.

15. Smetanin Y., Ul’yanov M. Determining the characteristics of kolmogorov complexity of time series: an approach based on symbolic descriptions. – 2013.


Для цитирования:


Алексеев В.А., Сметанин Ю.Г. О возможности восстановления периодического слова по подсловам фиксированной длины. Чебышевский сборник. 2021;22(1):57-66. https://doi.org/10.22405/2226-8383-2021-22-1-57-66

For citation:


Alekseev V.A., Smetanin Yu.G. On the possibility of a periodic word reconstruction from the subwords of fixed length. Chebyshevskii Sbornik. 2021;22(1):57-66. (In Russ.) https://doi.org/10.22405/2226-8383-2021-22-1-57-66

Просмотров: 13


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)