Generalised Entropies and Asymptotic Complexities of Languages

Yuri Kalnishkan; M V  Vyugin; Vladimir Vovk

doi:10.1016/j.ic.2014.01.001

Generalised Entropies and Asymptotic Complexities of Languages

Yuri Kalnishkan, M V Vyugin, Vladimir Vovk

Research output: Contribution to journal › Article › peer-review

947 Downloads (Pure)

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 language	English
Pages (from-to)	101–141
Number of pages	41
Journal	Information and Computation
Volume	237
Early online date	9 Jan 2014
DOIs	https://doi.org/10.1016/j.ic.2014.01.001
Publication status	Published - Oct 2014

Access to Document

10.1016/j.ic.2014.01.001

Accepted ManuscriptAccepted author manuscript, 676 KB

http://www.sciencedirect.com/science/article/pii/S0890540114000029

Cite this

@article{30e8d3bb6279436fb9b3db5c0dcf8a71,

title = "Generalised Entropies and Asymptotic Complexities of Languages",

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{\textquoteright}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.",

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

year = "2014",

month = oct,

doi = "10.1016/j.ic.2014.01.001",

language = "English",

volume = "237",

pages = "101–141",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Generalised Entropies and Asymptotic Complexities of Languages

AU - Kalnishkan, Yuri

AU - Vyugin, M V

AU - Vovk, Vladimir

PY - 2014/10

Y1 - 2014/10

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

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

U2 - 10.1016/j.ic.2014.01.001

DO - 10.1016/j.ic.2014.01.001

M3 - Article

SN - 0890-5401

VL - 237

SP - 101

EP - 141

JO - Information and Computation

JF - Information and Computation

ER -