31 citations · 83 across the 33 of their papers we have counts for
20 papers · 1 filter
Model Comparison Games for Generalized Quantifiers
Antti Kuusisto, Miguel Moreno, Matias Selin
We introduce three new model comparison games that characterize separability by first-order formulas with generalized quantifiers. The first is built on the Ehrenfeucht-Fraïssé gam…
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…
The power of clockings
Antti Kuusisto
We investigate the expressive power of a Turing-complete logic based on game-theoretic semantics. By defining suitable fragments and variants of the logic, we obtain a range of nat…