Geodesic
Algorithmic complexity of problems of optimal alphabetical coding for context-free languages
Diskretnaya Matematika, Tome 1 (1989) no. 2, pp. 38-51.

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

We consider a combinatorial-logical model of alphabetic coding that takes into account the structural properties of the language of the messages. As languages of the messages we consider the closest known extensions of regular languages – context-free (CF) languages and deterministic CF (DCF) languages. For classes of models of alphabetical coding of CF and DCF languages we prove the algorithmic undecidability of one of the basic problems of coding – the problem of optimal coding (in the sense of cost). We study the theoretical possibility of solving the problem of optimal coding for two forms of restrictions on the complexity of decoding: when decoding with finite delay and with finite-automaton decoding. We show that the restrictions imposed on decoding do not coincide for irregular models of languages and one does not include the other. 
@article{DM_1989_1_2_a3,
     author = {L. P. Zhil'tsova},
     title = {Algorithmic complexity of problems of optimal alphabetical coding for context-free languages},
     journal = {Diskretnaya Matematika},
     pages = {38--51},
     publisher = {mathdoc},
     volume = {1},
     number = {2},
     year = {1989},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1989_1_2_a3/}
}
TY  - JOUR
AU  - L. P. Zhil'tsova
TI  - Algorithmic complexity of problems of optimal alphabetical coding for context-free languages
JO  - Diskretnaya Matematika
PY  - 1989
SP  - 38
EP  - 51
VL  - 1
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1989_1_2_a3/
LA  - ru
ID  - DM_1989_1_2_a3
ER  - 
%0 Journal Article
%A L. P. Zhil'tsova
%T Algorithmic complexity of problems of optimal alphabetical coding for context-free languages
%J Diskretnaya Matematika
%D 1989
%P 38-51
%V 1
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1989_1_2_a3/
%G ru
%F DM_1989_1_2_a3
L. P. Zhil'tsova. Algorithmic complexity of problems of optimal alphabetical coding for context-free languages. Diskretnaya Matematika, Tome 1 (1989) no. 2, pp. 38-51. http://geodesic.mathdoc.fr/item/DM_1989_1_2_a3/