Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
type: Item
instance of: scholarly article
title: Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
zbMATH Open document ID: 0613.94006
published in: Problems of Information Transmission
publication date: 1986-01-01T00:00:00Z
review text: We consider the problem of noiseless coding of combinatorial (nonstochastic) sources. The cost of the optimal code is shown to equal to the Hausdorff dimension of the source. The same problem is solved with algorithmic constraints on the code in two settings: coding and decoding realized by Turing machines and by finite automata. The lower bounds on the cost of the code in these cases are expressed in terms of the Kolmogorov complexity and the quasi-entropy, respectively. Optimal codes are constructed for sources generated by formal grammars.
Mathematics Subject Classification ID: 94A29
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3993446
zbMATH Keywords: noiseless coding
zbMATH Keywords: cost of the optimal code
zbMATH Keywords: Turing machines
zbMATH Keywords: finite automata
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: quasi-entropy
zbMATH Keywords: sources generated by formal grammars
author: B. Ya. Ryabko
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 3993446