Generalized entropies and asymptotic complexities of languages. / Kalnishkan, Yuri; Vyugin, Michael V.; Vovk, Vladimir.

Proceedings of the Fifth Workshop on Information-Theoretic Methods in Science and Engineering. ed. / Steven de Rooij; Wojciech Kotlowski; Jorma Rissanen; Petri Millimaki; Teemu Roos; Kenji Yamanishi. Amsterdam : CWI, 2012. p. 44-47.

Research output: Chapter in Book/Report/Conference proceedingConference contribution



The talk explores connections between asymptotic complexity and generalised entropy. Asymptotic complexity of a language (a language is a set of finite or infinite strings) is a way of formalising the complexity of predicting the next element in a sequence: it is the loss per element of a strategy asymptotically optimal for that language. Generalised entropy extends Shannon entropy to arbitrary loss functions; it is the optimal expected loss given a distribution on possible outcomes. It turns out that the set of tuples of asymptotic complexities of a language w.r.t. different loss functions can be described by means of generalised entropies corresponding to the loss functions.
Original languageEnglish
Title of host publicationProceedings of the Fifth Workshop on Information-Theoretic Methods in Science and Engineering
EditorsSteven de Rooij, Wojciech Kotlowski, Jorma Rissanen, Petri Millimaki, Teemu Roos , Kenji Yamanishi
Place of PublicationAmsterdam
Number of pages4
Publication statusPublished - Sep 2012

ID: 9594509