Geodesic
On a~comparison of underdetermined alphabets
Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 34-36.

Voir la notice de l'article provenant de la source Math-Net.Ru

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: underdetermined alphabet, alphabets of equal strength, entropy of underdetermined data, Kolmogorov complexity. 
@article{PDMA_2014_7_a13,
     author = {L. A. Sholomov},
     title = {On a~comparison of underdetermined alphabets},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {34--36},
     publisher = {mathdoc},
     number = {7},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2014_7_a13/}
}
TY  - JOUR
AU  - L. A. Sholomov
TI  - On a~comparison of underdetermined alphabets
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2014
SP  - 34
EP  - 36
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2014_7_a13/
LA  - ru
ID  - PDMA_2014_7_a13
ER  - 
%0 Journal Article
%A L. A. Sholomov
%T On a~comparison of underdetermined alphabets
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2014
%P 34-36
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2014_7_a13/
%G ru
%F PDMA_2014_7_a13
L. A. Sholomov. On a~comparison of underdetermined alphabets. Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 34-36. http://geodesic.mathdoc.fr/item/PDMA_2014_7_a13/

[1] Kolmogorov A. N., “Tri podkhoda k opredeleniyu ponyatiya ‘kolichestvo informatsii’ ”, Problemy peredachi informatsii, 1:1 (1965), 3–11 | MR | Zbl

[2] Sholomov L. A., “Elementy teorii nedoopredelennoi informatsii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2009, no. 2, 18–42