The entropy of Łukasiewicz-languages

Ludwig Staiger

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 39.4 (2010): 621-639. <http://eudml.org/doc/92780>.

@article{Staiger2010,
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},
keywords = {Entropy of languages; Bernoulli measure of languages; codes; Łukasiewicz language},
language = {eng},
month = {3},
number = {4},
pages = {621-639},
publisher = {EDP Sciences},
title = {The entropy of Łukasiewicz-languages},
url = {http://eudml.org/doc/92780},
volume = {39},
year = {2010},
}

TY - JOUR
AU - Staiger, Ludwig
TI - The entropy of Łukasiewicz-languages
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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/92780
ER -

References

top
  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).  
  3. N. Chomsky and G.A. Miller, Finite-state languages. Inform. Control1 (1958) 91–112.  
  4. J. Devolder, M. Latteux, I. Litovski and L. Staiger, Codes and Infinite Words. Acta Cybernetica11 (1994) 241–256.  
  5. S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York (1974).  
  6. H. Fernau, Valuations of Languages, with Applications to Fractal Geometry. Theoret. Comput. Sci.137 (1995) 177–217.  
  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. Control29 (1975) 268–285.  
  10. F.P. Kaminger, The noncomputability of the channel capacity of context-sensitive languages. Inform. Control17 (1970) 175–182.  
  11. W. Kuich, On the entropy of context-free languages. Inform. Control16 (1970) 173–200.  
  12. M. Li and P.M.B. Vitányi, An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, New York (1993).  
  13. L. Staiger, On infinitary finite length codes. RAIRO-Inf. Theor. Appl.20 (1986) 483–494.  
  14. L. Staiger, Ein Satz über die Entropie von Untermonoiden. Theor. Comput. Sci.61 (1988) 279–282.  
  15. L. Staiger, Kolmogorov complexity and Hausdorff dimension. Inform. Comput.103 (1993) 159–194.  

NotesEmbed ?

top

You must be logged in to post comments.