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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Published

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kalnishkan, Y, Vyugin, MV & Vovk, V 2012, Generalized entropies and asymptotic complexities of languages. in S de Rooij, W Kotlowski, J Rissanen, P Millimaki, TR & K Yamanishi (eds), *Proceedings of the Fifth Workshop on Information-Theoretic Methods in Science and Engineering.* CWI, Amsterdam, pp. 44-47.

Kalnishkan, Y., Vyugin, M. V., & Vovk, V. (2012). Generalized entropies and asymptotic complexities of languages. In S. de Rooij, W. Kotlowski, J. Rissanen, P. Millimaki, T. R., & K. Yamanishi (Eds.), *Proceedings of the Fifth Workshop on Information-Theoretic Methods in Science and Engineering *(pp. 44-47). CWI.

Kalnishkan Y, Vyugin MV, Vovk V. Generalized entropies and asymptotic complexities of languages. In de Rooij S, Kotlowski W, Rissanen J, Millimaki P, TR, Yamanishi K, editors, Proceedings of the Fifth Workshop on Information-Theoretic Methods in Science and Engineering. Amsterdam: CWI. 2012. p. 44-47

@inproceedings{3d3f56fe9df242c7a06a2ef71ef3be36,

title = "Generalized entropies and asymptotic complexities of languages",

abstract = "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.",

author = "Yuri Kalnishkan and Vyugin, {Michael V.} and Vladimir Vovk",

note = "http://event.cwi.nl/witmse2012/proc.pdf",

year = "2012",

month = sep,

language = "English",

pages = "44--47",

editor = "{de Rooij}, Steven and Wojciech Kotlowski and Jorma Rissanen and Petri Millimaki and {Teemu Roos} and Kenji Yamanishi",

booktitle = "Proceedings of the Fifth Workshop on Information-Theoretic Methods in Science and Engineering",

publisher = "CWI",

}

TY - GEN

T1 - Generalized entropies and asymptotic complexities of languages

AU - Kalnishkan, Yuri

AU - Vyugin, Michael V.

AU - Vovk, Vladimir

N1 - http://event.cwi.nl/witmse2012/proc.pdf

PY - 2012/9

Y1 - 2012/9

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

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

M3 - Conference contribution

SP - 44

EP - 47

BT - Proceedings of the Fifth Workshop on Information-Theoretic Methods in Science and Engineering

A2 - de Rooij, Steven

A2 - Kotlowski, Wojciech

A2 - Rissanen, Jorma

A2 - Millimaki, Petri

A2 - , Teemu Roos

A2 - Yamanishi, Kenji

PB - CWI

CY - Amsterdam

ER -