5 citations · 6 across the 6 of their papers we have counts for
5 papers · 1 filter
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…
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…
Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality
Emanuel Kieroński, Antti Kuusisto
Uniform one-dimensional fragment UF1^= is a formalism obtained from first-order logic by limiting quantification to applications of blocks of existential (universal) quantifiers su…
Team Semantics and Recursive Enumerability
Antti Kuusisto
It is well known that dependence logic captures the complexity class NP, and it has recently been shown that inclusion logic captures P on ordered models. These results demonstrate…
One-dimensional fragment of first-order logic
Lauri Hella, Antti Kuusisto
We introduce a novel decidable fragment of first-order logic. The fragment is one-dimensional in the sense that quantification is limited to applications of blocks of existential (…