О числе реконструкций по подсловам в бинарном алфавите при наложении на один символ

Современные информационные технологии и ИТ-образование. 2020. Т. 16. № 2. С. 304–313.

Zhukova G., Сметанин Ю. Г., Ulyanov M.

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”.

Keywords: комбинаторика слов, символьная последовательность, symbolic sequence, сombinatorics on words, binary alphabet, reconstruction of a sequence, reconstruction of a sequences from their subsequences, бинарный алфавит, реконструкция последовательности, реконструкция последовательности по ее подпоследовательностям