| Abstrakt: | The main task of this thesis is to examine the use of transformation in solving problems with supplementary information. The thesis is a continuation of the research devoted to various aspects of information. It belongs to the part, where the topic of the research is the "usefulness" of the information, while as a tool used for the measurement of the usefulness is the descriptional complexity of deterministic finite automata. The results presented to this date relied on the fact, that the supplementary information is in the form, which can be used directly.
In this thesis, we propose a framework for studying the possibility to transform the instance of a problem to match the format of the advisory information. A widely used and quite general transformation device is an a-transducer. It turned out, that it is not always convenient to allow the use of nondeterminism in transformations. Therefore, we examine also the case, that the transformation device is a sequential transducer.
The thesis is devoted to the notion of information and to the question, how can its various aspects be defined, studied and measured. The proposed thesis develops a model for studying the usefulness of information also in cases, where it is not usable directly. This model allows to consider the earlier results about the usefulness of information as a special case and therefore allows a direct comparison with the previous model.
|
|---|