Relating description complexity to entropy

DOI10.1016/j.jcss.2024.103615MaRDI QIDQ6671671FDOQ6671671

Authors: Antti Kuusisto, Miikka Vilander 

Publication date: 27 January 2025

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Recommendations

• Entropy of formulas
• Shannon Entropy vs. Kolmogorov Complexity
• A note on entropy of logic
• The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws
• Generalised entropies and asymptotic complexities of languages

zbMATH Keywords

entropyinformation theorylogicrandomnessformula sizeformula size game

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Title not available (Why is that?)
• On Bernoulli sums and Bernstein polynomials
• An \(n!\) lower bound on formula size
• The number of finite relational structures
• Some equivalences between Shannon entropy and Kolmogorov complexity
• Entropy measures vs. Kolmogorov complexity
• Logical complexity of graphs: a survey
• An introduction to Kolmogorov complexity and its applications
• Satisfiability problem for modal logic with global counting operators coded in binary is \textsc{NExpTime}-complete
• On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics
• Formula size games for modal logic and \(\mu\)-calculus
• Title not available (Why is that?)

This page was built for publication: Relating description complexity to entropy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6671671)