License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.38
URN: urn:nbn:de:0030-drops-176903
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17690/
Go to the corresponding LIPIcs Volume Portal

Jaakkola, Reijo ; Kuusisto, Antti ; Vilander, Miikka

Relating Description Complexity to Entropy

pdf-format:
LIPIcs-STACS-2023-38.pdf (0.8 MB)

Abstract

We demonstrate some novel links between entropy and description complexity, a notion referring to the minimal formula length for specifying given properties. Let MLU be the logic obtained by extending propositional logic with the universal modality, and let GMLU be the corresponding extension with the ability to count. In the finite, MLU is expressively complete for specifying sets of variable assignments, while GMLU is expressively complete for multisets. We show that for MLU, the model classes with maximal Boltzmann entropy are the ones with maximal description complexity. Concerning GMLU, we show that expected Boltzmann entropy is asymptotically equivalent to expected description complexity multiplied by the number of proposition symbols considered. To contrast these results, we prove that this link breaks when we move to considering first-order logic FO over vocabularies with higher-arity relations. To establish the aforementioned result, we show that almost all finite models require relatively large FO-formulas to define them. Our results relate to links between Kolmogorov complexity and entropy, demonstrating a way to conceive such results in the logic-based scenario where relational structures are classified by formulas of different sizes.

BibTeX - Entry

@InProceedings{jaakkola_et_al:LIPIcs.STACS.2023.38,
  author =	{Jaakkola, Reijo and Kuusisto, Antti and Vilander, Miikka},
  title =	{{Relating Description Complexity to Entropy}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17690},
  URN =		{urn:nbn:de:0030-drops-176903},
  doi =		{10.4230/LIPIcs.STACS.2023.38},
  annote =	{Keywords: finite model theory, entropy, formula size, randomness, formula size game}
}

Keywords: finite model theory, entropy, formula size, randomness, formula size game
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI