О числе реконструкций по подсловам в бинарном алфавите при наложении на один символ
Authors: Жукова Г.Н. , Сметанин Ю.Г. , Ульянов М.В. 
Published: December 2024

Рассмотрена задача получения точных оценок числа реконструкций для слов над бинарным алфавитом. Подслова различной длины из заданного множества соединяются методом наложения концевых символов. Соединять можно только такую пару подслов, у которых последний символ первого подслова совпадает с первым символом второго. При наложении пары подходящих подслов на один символ из двух одинаковых символов (в конце первого и в начале второго подслова) в реконструкцию входит только один. Предложен подход, основанный на рассмотрении усеченных подслов, состоящих из префикса и суффикса данного подслова, имеющих длину один. При построении реконструкции вместо самих подслов из заданного множества соединяются усеченные слова вида «00», «01», «10» и «11». Число реконструкций находится в предположении, что каждое из усеченных подслов соответствует уникальному подслову в заданном множестве подслов. В результате при соединении слов «00» и «00» возможны две реконструкции, соответствующие соединению исходных подслов «0x0» и «0y0» в «0x0y0» и «0y0x0», где x и y — различные последовательности символов бинарного алфавита, одна из которых может быть пустой (но не обе одновременно). Такой подход позволил определить условия существования реконструкции по заданному множеству подслов различной длины. Показано, при каких условиях, касающихся количества усеченных подслов каждого вида, реконструкция невозможна. Например, невозможна реконструкция по множеству подслов, содержащему только подслова вида «00» и «11». Также невозможно соединить все подслова заданного множества, если число усеченных подслов вида «01» и «10» отличается больше, чем на один. Для различных случаев, допускающих полную реконструкцию, получены формулы точного числа реконструкций. Точное число реконструкций зависит от наличия или отсутствия подслов, соответствующих усеченным подсловам каждого вида. Поскольку возможность реконструкции главным образом зависит от соотношения числа подслов вида «01» и «10», то отдельно была рассмотрена модель с возможностью инверсий слов. Предполагается, что множество подслов для реконструкции содержит только слова вида вида «00», «01» «00», Часть слов вида «01» записывается в обратном порядке и становится словами вида «10». Если слов «01» было четное число, то в «01» преобразуется половина слов «01», иначе — половина от ближайшего четного числа. В последнем случае из множества подслов вида «01» получается два варианта наборов подслов вида «01» и «10», в одном больше подслов «01», в другом — «10». Для каждого случая приведены формулы точного числа реконструкций при условии уникальности подслов в заданном множестве, а также несимметричности подслов, порождающих усеченные подслова вида «00» и «11».

The problem of obtaining accurate estimates of the number of reconstructions for words over a binary alphabet is considered. Subwords of different lengths from a given set are joined by the method of overlapping end characters. It is only possible to connect a pair of subwords where the last character of the first subword is the same as the first character of the second. When superimposing a pair of suitable subwords on one character of two identical ones (at the end of the first and at the beginning of the second subword) only one, is included in the reconstruction. An approach based on combining truncated subwords consisting of the first and last characters of a subword is proposed. When building a reconstruction, instead of the subwords from a given set, truncated words of the form “00”, “01”, “10” and “11” are connected. The number of reconstructions is under the assumption that each of the truncated subwords corresponds to a unique subword in a given set of subwords. As a result, when combining the words “00” and “00”, two reconstructions are possible, corresponding to combining the original subwords “0x0” and “0y0” into “0x0y0” and “0y0x0”, where x and y are different sequences of binary alphabet characters, one of which may be empty (but not both simultaneously). Such an approach made it possible to determine the conditions for the existence of reconstruction from a given set of subwords of various lengths. It is noted under what conditions, concerning the number of truncated subwords of each type, reconstruction is impossible. For example, reconstruction by a set of subwords containing only subwords of the form “00” and “11” is not possible. It is also impossible to combine all the subwords of a given set if the number of truncated subwords of the form “01” and “10” differs by more than one. For various cases allowing for complete reconstruction, formulas of the exact number of reconstructions are obtained. The exact number of reconstructions depends on the presence or absence of subwords corresponding to truncated subwords of each type. Since the possibility of reconstruction mainly depends on the ratio of the number of subwords of the form “01” and “10”, a model with the possibility of word inversions was also considered. It is assumed that the set of subwords for reconstruction contains only words of the form “00”, “01” and “11”. Some of the words of the form “01” are written in the reverse order and become words of the form “10”. If the words “01” were an even number, then half of the words “01” would be converted to “01”, otherwise, half of the nearest even number would be. In the latter case, from the set of subwords of the form “01”, two variants of the sets of subwords of the form “01” and “10” are obtained, in one, there are more subwords “01”, in the other “10”. For each case, formulas are given for the exact number of reconstructions, provided that the subwords in the given set are unique, as well as the asymmetry of the subwords generating truncated subwords of the form “00” and “11”.