On a comparison of underdetermined alphabets

For underdetermined alphabets, the following two concepts are defined: (a) one alphabet is stronger than another, and (b) two alphabets have equal strength. In case (b), a solution of an optimal compression problem for one of the alphabets in fact is a solution of the same problem for the other. To define concepts (a) and (b), several approaches are used. The functional approach is based on expressibility of one alphabet via another; three other approaches - combinatorial, statistical, and algorithmic - are terminologically connected with Kolmogorov's approaches to the notion of the amount of information. It is proved that all considered approaches to comparison of alphabets are equivalent, and concepts (a) and (b) allow polynomial time verification.

Keywords

Authors

References