10 citations · 17 across the 12 of their papers we have counts for
13 papers
Structural vs. computational complexity
Johanna N. Y. Franklin, Dino Rossegger, Dan Turetsky
We consider highness in the context of computable structure theory and, particularly, the Scott rank of a structure. We define highness for Scott rank and highness for computably d…
Scott Analysis below the Vaught Ordinal
David Gonzalez, Dino Rossegger, Dan Turetsky
We develop new tools for determining the existence of models of specific Scott ranks under countability conditions. Using these, we improve a result of Sacks by showing that any co…
Classifying the complexity of models of arithmetic
David Gonzalez, Mateusz Łełyk, Dino Rossegger +1
We classify the possible Scott complexities for models of Peano arithmetic. We construct models of particular complexities by first giving a complete Scott analysis of colored line…
Hausdorff dimension and countable Borel equivalence relations
Andrew Marks, Dino Rossegger, Theodore Slaman
We show that if is a countable Borel equivalence relation on , then there is a closed subset of Hausdorff dimension so that $E \restrictio…
Learning Equivalence Relations on Polish Spaces
Dino Rossegger, Theodore Slaman, Tomasz Steifer
We investigate natural variations of behaviourally correct learning and explanatory learning -- two learning paradigms studied in algorithmic learning theory -- that allow us to ``…
The Borel complexity of the class of models of first-order theories
Uri Andrews, David Gonzalez, Steffen Lempp +2
We investigate the descriptive complexity of the set of models of first-order theories. Using classical results of Knight and Solovay, we give a sharp condition for complete theori…
Scott sentence complexities of linear orderings
David Gonzalez, Dino Rossegger
We study possible Scott sentence complexities of linear orderings using two approaches. First, we investigate the effect of the Friedman-Stanley embedding on Scott sentence complex…
Degrees of categoricity and treeable degrees
Barbara F. Csima, Dino Rossegger
We give a characterization of the strong degrees of categoricity of computable structures greater or equal to . They are precisely the \emph{treeable} degrees -- the l…
The structural complexity of models of arithmetic
Antonio Montalbán, Dino Rossegger
We calculate the possible Scott ranks of countable models of Peano arithmetic. We show that no non-standard model can have Scott rank less than and that non-standard models of…
Relations enumerable from positive information
Barbara F. Csima, Luke MacLean, Dino Rossegger
We study countable structures from the viewpoint of enumeration reducibility. Since enumeration reducibility is based on only positive information, in this setting it is natural to…
Positive enumerable functors
Barbara Csima, Dino Rossegger, Zhi Ying "Daniel" Yu
We study reductions well suited to compare structures and classes of structures with respect to properties based on enumeration reducibility. We introduce the notion of a positive…
The complexity of Scott sentences of scattered linear orders
Rachael Alvir, Dino Rossegger
Given a countable scattered linear order of Hausdorff rank we show that it has a Scott sentence. Ash calculated the back and forth relations for al…
On functors enumerating structures
Dino Rossegger
We study a new notion of reduction between structures called enumerable functors related to the recently investigated notion of computable functors. Our main result shows that enum…