Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On entropy and optimal coding cost for stochastic language

Zhiltsova L.

Fundamenta Informaticae

1998

Vol. 36, nr 2,3

285-305

We investigate questions, relating to optimal binary coding of a language, for which a probability distribution is given on its words (for a stochastic language). As optimal we understand the coding, which gives minimum of mathematical expectation of a length of the coded word, or minimum of the coding cost. For any stochastic language with a finite value of the entropy we establish lower and upper bounds of the optimal coding cost, dependent only on the entropy, and we prove their unimprovability. For any stochastic context-free language with unique derivation it is found necessary and sufficient condition of existence of finite values of the optimal coding cost and the entropy. Also an effective method of calculation of the entropy is found for the case when the considered condition holds.