A monotone connection between model class size and description length

Reijo Jaakkola, Antti Kuusisto, Miikka Vilander

This paper links sizes of model classes to the minimum lengths of their defining formulas, that is, to their description complexities. Limiting to models with a fixed domain of siz…