On entropy and optimal coding cost for stochastic language

• Autorzy: Zhiltsova L.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

stochastic language; context-free grammar; entropy; optimal coding

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1998
• Tom: Vol. 36, nr 2,3
• Strony: 285--305
• Opis fizyczny: bibliogr. 9 poz.

Twórcy

autor

Zhiltsova L.

• Chair of Computer Science, Nizhni Novgorod State Pedagogical University, 1, Uljanova St., Nizhni Novgorod, 603600, Russia,