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

Аннотация

Рассмотрена задача реконструкции слов из конечного алфавита по частичной информации при дополнительных ограничениях на допустимые слова.
А именно, ставится задача о восстановлении периодического слова по мультимножеству его подслов одной длины.
Для некоторых видов частичной информации и ограничений получены условия однозначной реконструкции.
Показано, что периодическое слово с периодом $$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)$$.