| main| | new issue| | archive| | editorial board| | for the authors| | publishing house| |
 Ðóññêèé |
 |
 |
 |
 |
 |
 |
|
|
ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 4. Vol. 24. 2018
Yu. G. Smetanin, D. Sc., Chief Researcher, e-mail: ysmetanin@rambler.ru, Federal Research Center "Informatics and Control", Moscow, Russia, M. V. Uljanov, Ph. D., Leading Researcher, e-mail: muljanov@mail.ru, Institute of Control Sciences, Moscow, Russia, A. S. Pestova, Graduate Student, National Research University Higher School of Economics, Moscow, Russia
On the Number of Possible Reconstructions of Words Using Subwords with Windows of Different Shift
The objects studied in the article are finite words over binary alphabet. These words are symbolic codes of the objects and processes under study. Under the assumption that only fragments (subwords) of such descriptions are known to the researcher, the problem of reconstructing the complete code is of interest. From the point of view of combinatorics of words, reconstructing the description using disjointed fragments of observations is the task of reconstructing a word using known subwords. To solve it, one needs to accept the hypothesis about the value of the sliding window that generates the subwords. Obviously, such a reconstruction can be multivalued. The dependence of the mathematical expectation for the number of possible reconstructions on the value of the shift parameter is proposed in the article. The obtained estimates make can be used for evaluating the relationship between the "density" of the available fragmentary information and the number of alternative solutions of the reconstruction problem. They are useful from the point of the possibility of determining the number of alternatives before the beginning of the reconstruction process. The estimations may prove to be important in decision-making problems which demand the restored complete information. Possible further studies are related to the analysis of the effect of additional information, presented in the form of prohibitions of certain reconstruction options, on the number of possible reconstructions.
Keywords: words over a finite alphabet, sliding window of arbitrary shift, reconstruction of words, estimation of the number of reconstructions
P. 233–238