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 : https://doi.org/10.1051/ita:2005032
Classification : 68Q30,  68Q45,  94A17
Mots clés : 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},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {4},
     year = {2005},
     doi = {10.1051/ita:2005032},
     zbl = {1073.68670},
     language = {en},
     url = {http://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
DA  - 2005///
SP  - 621
EP  - 639
VL  - 39
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2005032/
UR  - https://zbmath.org/?q=an%3A1073.68670
UR  - https://doi.org/10.1051/ita:2005032
DO  - 10.1051/ita:2005032
LA  - en
ID  - ITA_2005__39_4_621_0
ER  - 
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. http://www.numdam.org/articles/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). | MR 797069 | Zbl 0587.68066

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

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

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

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

[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 0361.94030

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

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

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

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

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

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

Cité par Sources :