Efficient reconstruction of sequences from their subsequences or supersequences
Аннотация:
В статье рассматриваютя две комбинаторные задачи для множества Fqn последовательностей длины n над алфавитом Fq={0,1,...,q-1}. Для любых целых неотрицательных чисел n и t найдена максимальная мощность Nq-(n,t) множества общих подпоследовательностей длины n-t и максимальная мощность Nq+(n,t) множества общих надпоследовательностей длины n+t двух различных последовательностей из Fqn. Число Nq-(n,t)+1 (соответственно Nq+(n,t)+1) равно минимальному числу N различных подпоследовательностей длины n-t (надпоследовательностей длины n+t) неизвестной последовательности X ∈ Fqn, которые достаточны для ее восстановления. Приведены простые алгоритмы восстановления X ∈ Fqn по Nq-(n,t)+1 ее подпоследовательностям длины n-t и по Nq+(n,t)+1 ее надпоследовательностям длины n+t.
Ключевые слова:
последовательность, подпоследовательность, надпоследовательность, общая подпоследовательность, восстановление, алгоритмы.
