The entropy of Łukasiewicz-languages

Ludwig Staiger

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

  • Volume: 39, Issue: 4, page 621-639
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Staiger, Ludwig. "The entropy of Łukasiewicz-languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.4 (2005): 621-639. <http://eudml.org/doc/244905>.

@article{Staiger2005,
abstract = {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.},
author = {Staiger, Ludwig},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {entropy of languages; Bernoulli measure of languages; codes; Łukasiewicz language},
language = {eng},
number = {4},
pages = {621-639},
publisher = {EDP-Sciences},
title = {The entropy of Łukasiewicz-languages},
url = {http://eudml.org/doc/244905},
volume = {39},
year = {2005},
}

TY - JOUR
AU - Staiger, Ludwig
TI - The entropy of Łukasiewicz-languages
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2005
PB - EDP-Sciences
VL - 39
IS - 4
SP - 621
EP - 639
AB - 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.
LA - eng
KW - entropy of languages; Bernoulli measure of languages; codes; Łukasiewicz language
UR - http://eudml.org/doc/244905
ER -

References

top
  1. [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. [2] J. Berstel and D. Perrin, Theory of Codes. Academic Press, Orlando (1985). Zbl0587.68066MR797069
  3. [3] N. Chomsky and G.A. Miller, Finite-state languages. Inform. Control 1 (1958) 91–112. Zbl0081.14503
  4. [4] J. Devolder, M. Latteux, I. Litovski and L. Staiger, Codes and Infinite Words. Acta Cybernetica 11 (1994) 241–256. Zbl0938.68691
  5. [5] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York (1974). Zbl0317.94045MR530382
  6. [6] H. Fernau, Valuations of Languages, with Applications to Fractal Geometry. Theoret. Comput. Sci. 137 (1995) 177–217. Zbl0873.68110
  7. [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. [8] R. Johannesson, Informations theorie. Addison-Wesley (1992). 
  9. [9] J. Justesen and K. Larsen, On Probabilistic Context-Free Grammars that Achieve Capacity. Inform. Control 29 (1975) 268–285. Zbl0361.94030
  10. [10] F.P. Kaminger, The noncomputability of the channel capacity of context-sensitive languages. Inform. Control 17 (1970) 175–182. Zbl0196.01802
  11. [11] W. Kuich, On the entropy of context-free languages. Inform. Control 16 (1970) 173–200. Zbl0193.32603
  12. [12] M. Li and P.M.B. Vitányi, An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, New York (1993). Zbl0805.68063MR1238938
  13. [13] L. Staiger, On infinitary finite length codes. RAIRO-Inf. Theor. Appl. 20 (1986) 483–494. Zbl0628.68056
  14. [14] L. Staiger, Ein Satz über die Entropie von Untermonoiden. Theor. Comput. Sci. 61 (1988) 279–282. Zbl0661.68075
  15. [15] L. Staiger, Kolmogorov complexity and Hausdorff dimension. Inform. Comput. 103 (1993) 159–194. Zbl0789.68076

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.