Part 3. Mathematical models

Criterion for almost complete prediction of a superword in a multi-valued alphabet

I. Vedernikov


Abstract: The machine predicts the next character of the input sequence if it outputs that character the moment before. The present paper considers whether an arbitrary superword in multivalued alphabet can be almost completely predicted or not. The paper provides a theorem that enables to restrict the class of machines, with the help of which superwords are predicted. Moreover, the paper presents the criterion for almost complete predicting.

Keywords: almost complete predicting, predicting machine, prediction of superwords by a machine, criterion for predicting.