Relating description complexity to entropy
type: Item
instance of: scholarly article
title: Relating description complexity to entropy
DOI: 10.1016/j.jcss.2024.103615
author: Q6168479
author: Antti Kuusisto
author: Miikka Vilander
published in: Journal of Computer and System Sciences
publication date: 2025-01-27T00:00:00Z
Mathematics Subject Classification ID: 68-XX
zbMATH DE Number: 7975149
zbMATH Keywords: formula size
zbMATH Keywords: logic
zbMATH Keywords: entropy
zbMATH Keywords: information theory
zbMATH Keywords: randomness
zbMATH Keywords: formula size game
MaRDI profile type: MaRDI publication profile
cites work: Some equivalences between Shannon entropy and Kolmogorov complexity
cites work: An introduction to Kolmogorov complexity and its applications
cites work: Entropy measures vs. Kolmogorov complexity
cites work: On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics
cites work: Satisfiability problem for modal logic with global counting operators coded in binary is \textsc{NExpTime}-complete
cites work: Applications of matrix methods to the theory of lower bounds in computational complexity
cites work: An n ! lower bound on formula size
cites work: Formula size games for modal logic and μ-calculus
cites work: Q5882064
cites work: Q4457477
cites work: Q5538132
cites work: Q3843987
cites work: On Bernoulli sums and Bernstein polynomials
cites work: The number of finite relational structures
cites work: Logical complexity of graphs: a survey
cites work: Q4850061
description: scientific article; zbMATH DE number 7975149