The entropy of Łukasiewicz-languages
Staiger, Ludwig
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005), p. 621-639 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2005-01-01
DOI : https://doi.org/10.1051/ita:2005032
Classification:  68Q30,  68Q45,  94A17 
@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},
     volume = {39},
     year = {2005},
     pages = {621-639},
     doi = {10.1051/ita:2005032},
     zbl = {1073.68670},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 621-639. doi : 10.1051/ita:2005032. http://gdmltest.u-ga.fr/item/ITA_2005__39_4_621_0/

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