no. 4
The entropy of Łukasiewicz-languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 4, pp. 621-639

The paper presents an elementary approach for the calculation of the entropy of a class of languages. This approach is based on the consideration of roots of a real polynomial and is also suitable for calculating the Bernoulli measure. The class of languages we consider here is a generalisation of the Łukasiewicz language.

DOI : 10.1051/ita:2005032
Classification : 68Q30, 68Q45, 94A17
Keywords: entropy of languages, Bernoulli measure of languages, codes, Łukasiewicz language 
@article{ITA_2005__39_4_621_0,
     author = {Staiger, Ludwig},
     title = {The entropy of {{\L}ukasiewicz-languages}},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {621--639},
     year = {2005},
     publisher = {EDP Sciences},
     volume = {39},
     number = {4},
     doi = {10.1051/ita:2005032},
     zbl = {1073.68670},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita:2005032/}
}
TY  - JOUR
AU  - Staiger, Ludwig
TI  - The entropy of Łukasiewicz-languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2005
SP  - 621
EP  - 639
VL  - 39
IS  - 4
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ita:2005032/
DO  - 10.1051/ita:2005032
LA  - en
ID  - ITA_2005__39_4_621_0
ER  - 
%0 Journal Article
%A Staiger, Ludwig
%T The entropy of Łukasiewicz-languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2005
%P 621-639
%V 39
%N 4
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ita:2005032/
%R 10.1051/ita:2005032
%G en
%F ITA_2005__39_4_621_0
Staiger, Ludwig. The entropy of Łukasiewicz-languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 4, pp. 621-639. doi: 10.1051/ita:2005032

[1] J.-M. Autebert, J. Berstel and L. Boasson, Context-Free Languages and Pushdown Automata, in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin 1 (1997) 111-174.

[2] J. Berstel and D. Perrin, Theory of Codes. Academic Press, Orlando (1985). | Zbl | MR

[3] N. Chomsky and G.A. Miller, Finite-state languages. Inform. Control 1 (1958) 91-112. | Zbl

[4] J. Devolder, M. Latteux, I. Litovski and L. Staiger, Codes and Infinite Words. Acta Cybernetica 11 (1994) 241-256. | Zbl

[5] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York (1974). | Zbl | MR

[6] H. Fernau, Valuations of Languages, with Applications to Fractal Geometry. Theoret. Comput. Sci. 137 (1995) 177-217. | Zbl

[7] G. Hansel, D. Perrin and I. Simon, Entropy and compression, in STACS'92, edited by A. Finkel and M. Jantzen. Lect. Notes Comput. Sci. 577 (1992) 515-530.

[8] R. Johannesson, Informations theorie. Addison-Wesley (1992).

[9] J. Justesen and K. Larsen, On Probabilistic Context-Free Grammars that Achieve Capacity. Inform. Control 29 (1975) 268-285. | Zbl

[10] F.P. Kaminger, The noncomputability of the channel capacity of context-sensitive languages. Inform. Control 17 (1970) 175-182. | Zbl

[11] W. Kuich, On the entropy of context-free languages. Inform. Control 16 (1970) 173-200. | Zbl

[12] M. Li and P.M.B. Vitányi, An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, New York (1993). | Zbl | MR

[13] L. Staiger, On infinitary finite length codes. RAIRO-Inf. Theor. Appl. 20 (1986) 483-494. | Zbl | Numdam | EuDML

[14] L. Staiger, Ein Satz über die Entropie von Untermonoiden. Theor. Comput. Sci. 61 (1988) 279-282. | Zbl

[15] L. Staiger, Kolmogorov complexity and Hausdorff dimension. Inform. Comput. 103 (1993) 159-194. | Zbl

Cité par Sources :