2 citations · 3 across the 16 of their papers we have counts for
5 papers · 1 filter
Description Complexity of Unary Structures in First-Order Logic with Links to Entropy
Reijo Jaakkola, Antti Kuusisto, Miikka Vilander
The description complexity of a model is the length of the shortest formula that defines the model. We study the description complexity of unary structures in first-order logic FO,…
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…
Relating description complexity to entropy
Reijo Jaakkola, Antti Kuusisto, Miikka Vilander
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 o…
First-order logic with self-reference
Reijo Jaakkola, Antti Kuusisto
We consider an extension of first-order logic with a recursion operator that corresponds to allowing formulas to refer to themselves. We investigate the obtained language under two…
Algebraic classifications for fragments of first-order logic and beyond
Reijo Jaakkola, Antti Kuusisto
Complexity and decidability of logics is a major research area involving a huge range of different logical systems. This calls for a unified and systematic approach for the field.…