Современные информационные технологии и IT-образование (Sep 2020)
On the Number of Subword Reconstructions in the Binary Alphabet when Superimposed on one Character
Abstract
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
