Generalised Entropies and Asymptotic Complexities of Languages. / Kalnishkan, Yuri; Vyugin, M V ; Vovk, Vladimir.

In: Information and Computation, Vol. 237, 10.2014, p. 101–141.

Research output: Contribution to journalArticle

Published

Documents

  • entropies34

    Accepted author manuscript, 675 KB, PDF-document

Links

Abstract

In this paper the concept of asymptotic complexity of languages is introduced. This concept formalises the notion of learnability in a particular environment and generalises Lutz and Fortnow’s concepts of predictability and dimension. Then asymptotic complexities in different prediction environments are compared by describing the set of all pairs of asymptotic complexities w.r.t. different environments. A geometric characterisation in terms of generalised entropies is obtained and thus the results of Lutz and Fortnow are generalised.
Original languageEnglish
Pages (from-to)101–141
JournalInformation and Computation
Volume237
Early online date9 Jan 2014
DOIs
StatePublished - Oct 2014
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 5106405