Dino Rossegger
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Dino Rossegger has a total of 28 co-authors. Here are the top co-authors by number of shared publications:
- Ekaterina Fokina
Technische Universität Wien
11 shared publications - Nikolay Bazhenov
Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
8 shared publications - Luca San Mauro
University of Bari
6 shared publications - Alexandra A. Soskova
Sofia University
4 shared publications - Stefan Vatev
Sofia University
4 shared publications - Barbara F. Csima
DEPARTMENT OF PURE MATHEMATICS UNIVERSITY OF WATERLOO 200 UNIVERSITY AVENUE WEST WATERLOO, ON N2L 3G1, CANADAURL: https://uwaterloo.ca/scholar/csima
3 shared publications
Latest Publications
- Open Access
Dichotomy results for classes of countable graphs
We study classes of countable graphs where every member does not contain a given finite graph as an induced subgraph -- denoted by $\mathsf{Free}(\mathcal{G})$ for a given finite graph $\mathcal{G}$. Our main results establish a structural dichotomy for such classes: If $\mathcal{G}$ is not an induced subgraph of $\mathcal{P}_4$, then $\mathsf{Free}(\mathcal{G})$ is on top under effective bi-interpretability, implying that the members of $\mathsf{Free}(\mathcal{G})$ exhibit the full range of structural and computational behaviors. In contrast, if $\mathcal{G}$ is an induced subgraph of $\mathcal{P}_4$, then $\mathsf{Free}(\mathcal{G})$ is structurally simple, as witnessed by the fact that every member satisfies the computable embeddability condition. This dichotomy is mirrored in the finite setting when one considers combinatorial and complexity-theoretic properties. Specifically, it is known that $\mathsf{Free}(\mathcal{G})^{fin}$ is complete for graph isomorphism and not a well-quasi-order under embeddability whenever $\mathcal{G}$ is not an induced subgraph of $\mathcal{P}_4$, while in all other cases $\mathsf{Free}(\mathcal{G})^{fin}$ forms a well-quasi-order and the isomorphism problem for $\mathsf{Free}(\mathcal{G})^{fin}$ is solvable in polynomial time.Open AccessDichotomy results for classes of countable graphs
We study classes of countable graphs where every member does not contain a given finite graph as an induced subgraph -- denoted by $\mathsf{Free}(\mathcal{G})$ for a given finite graph $\mathcal{G}$. Our main results establish a structural dichotomy for such classes: If $\mathcal{G}$ is not an induced subgraph of $\mathcal{P}_4$, then $\mathsf{Free}(\mathcal{G})$ is on top under effective bi-interpretability, implying that the members of $\mathsf{Free}(\mathcal{G})$ exhibit the full range of structural and computational behaviors. In contrast, if $\mathcal{G}$ is an induced subgraph of $\mathcal{P}_4$, then $\mathsf{Free}(\mathcal{G})$ is structurally simple, as witnessed by the fact that every member satisfies the computable embeddability condition. This dichotomy is mirrored in the finite setting when one considers combinatorial and complexity-theoretic properties. Specifically, it is known that $\mathsf{Free}(\mathcal{G})^{fin}$ is complete for graph isomorphism and not a well-quasi-order under embeddability whenever $\mathcal{G}$ is not an induced subgraph of $\mathcal{P}_4$, while in all other cases $\mathsf{Free}(\mathcal{G})^{fin}$ forms a well-quasi-order and the isomorphism problem for $\mathsf{Free}(\mathcal{G})^{fin}$ is solvable in polynomial time. - Open Access
Uniformity in learning structures
The standard framework for studying learning problems on algebraic structures assumes that the structures in the target family are pairwise nonisomorphic. Under this assumption, the most widely investigated learning criterion--Ex-learning--becomes inherently equivalent to the well-known paradigm of Bc-learning. This paper explores what happens when the nonisomorphism requirement is removed and analyzes the extent to which these two learning criteria remain uniformly equivalent.
Open AccessUniformity in learning structures
The standard framework for studying learning problems on algebraic structures assumes that the structures in the target family are pairwise nonisomorphic. Under this assumption, the most widely investigated learning criterion--Ex-learning--becomes inherently equivalent to the well-known paradigm of Bc-learning. This paper explores what happens when the nonisomorphism requirement is removed and analyzes the extent to which these two learning criteria remain uniformly equivalent.
- 25 November 2025
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 154 (2) , 883-892
Hausdorff dimension and countable Borel equivalence relations
We show that if E E is a countable Borel equivalence relation on R n \mathbb {R}^n , then there is a closed subset A ⊆ [ 0 , 1 ] n A \subseteq [0,1]^n of Hausdorff dimension n n so that E ↾ A E \restriction A is smooth. More generally, if ≤ Q \leq _Q is a locally countable Borel quasi-order on 2 ω 2^\omega and g g is any gauge function of lower order than the identity, then there is a closed set A A so that A A is an antichain in ≤ Q \leq _Q and H g ( A ) > 0 H^g(A) > 0 .
- 25 November 2025
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 154 (2) , 883-892
Hausdorff dimension and countable Borel equivalence relations
We show that if E E is a countable Borel equivalence relation on R n \mathbb {R}^n , then there is a closed subset A ⊆ [ 0 , 1 ] n A \subseteq [0,1]^n of Hausdorff dimension n n so that E ↾ A E \restriction A is smooth. More generally, if ≤ Q \leq _Q is a locally countable Borel quasi-order on 2 ω 2^\omega and g g is any gauge function of lower order than the identity, then there is a closed set A A so that A A is an antichain in ≤ Q \leq _Q and H g ( A ) > 0 H^g(A) > 0 .
- 17 July 2025
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 153 (09) , 4013-4024
The Borel complexity of the class of models of first-order theories
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 theories to have a Π ω 0 \boldsymbol \Pi _\omega ^0 -complete set of models. In particular, any sequential theory (a class of foundational theories isolated by Pudlák) has a Π ω 0 \boldsymbol \Pi _\omega ^0 -complete set of models. We also give sharp conditions for theories to have a Π n 0 \boldsymbol \Pi ^0_n -complete set of models.
- 17 July 2025
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 153 (09) , 4013-4024
The Borel complexity of the class of models of first-order theories
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 theories to have a Π ω 0 \boldsymbol \Pi _\omega ^0 -complete set of models. In particular, any sequential theory (a class of foundational theories isolated by Pudlák) has a Π ω 0 \boldsymbol \Pi _\omega ^0 -complete set of models. We also give sharp conditions for theories to have a Π n 0 \boldsymbol \Pi ^0_n -complete set of models.
- Open Access
- 3 February 2025
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-19
LEARNING EQUIVALENCE RELATIONS ON POLISH SPACES
We investigate natural variations of behaviourally correct learning and explanatory learning—two learning paradigms studied in algorithmic learning theory—that allow us to “learn” equivalence relations on Polish spaces. We give a characterization of the learnable equivalence relations in terms of their Borel complexity and show that the behaviourally correct and explanatory learnable equivalence relations coincide both in uniform and non-uniform versions of learnability and provide a characterization of the learnable equivalence relations in terms of their Borel complexity. We also show that the set of uniformly learnable equivalence relations is $\boldsymbol {\Pi }^1_1$ -complete in the codes and study the learnability of several equivalence relations arising naturally in logic as a case study.- 3 February 2025
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-19
Open AccessLEARNING EQUIVALENCE RELATIONS ON POLISH SPACES
We investigate natural variations of behaviourally correct learning and explanatory learning—two learning paradigms studied in algorithmic learning theory—that allow us to “learn” equivalence relations on Polish spaces. We give a characterization of the learnable equivalence relations in terms of their Borel complexity and show that the behaviourally correct and explanatory learnable equivalence relations coincide both in uniform and non-uniform versions of learnability and provide a characterization of the learnable equivalence relations in terms of their Borel complexity. We also show that the set of uniformly learnable equivalence relations is $\boldsymbol {\Pi }^1_1$ -complete in the codes and study the learnability of several equivalence relations arising naturally in logic as a case study. - 10 January 2025
- Published by Cambridge University Press (CUP) in The Bulletin of Symbolic Logic
- Vol. 31 (3) , 462-487
FEFERMAN’S COMPLETENESS THEOREM
Feferman proved in 1962 [6] that any arithmetical theorem is a consequence of a suitable transfinite iteration of full uniform reflection of $\mathsf {PA}$ . This result is commonly known as Feferman’s completeness theorem. The purpose of this paper is twofold. On the one hand this is an expository paper, giving two new proofs of Feferman’s completeness theorem that, we hope, shed light on this mysterious and often overlooked result. On the other hand, we combine one of our proofs with results from computable structure theory due to Ash and Knight to give sharp bounds on the order types of well-orders necessary to attain the completeness for levels of the arithmetical hierarchy.- 10 January 2025
- Published by Cambridge University Press (CUP) in The Bulletin of Symbolic Logic
- Vol. 31 (3) , 462-487
FEFERMAN’S COMPLETENESS THEOREM
Feferman proved in 1962 [6] that any arithmetical theorem is a consequence of a suitable transfinite iteration of full uniform reflection of $\mathsf {PA}$ . This result is commonly known as Feferman’s completeness theorem. The purpose of this paper is twofold. On the one hand this is an expository paper, giving two new proofs of Feferman’s completeness theorem that, we hope, shed light on this mysterious and often overlooked result. On the other hand, we combine one of our proofs with results from computable structure theory due to Ash and Knight to give sharp bounds on the order types of well-orders necessary to attain the completeness for levels of the arithmetical hierarchy.- 13 December 2024
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 90 (4) , 1563-1592
SCOTT SENTENCE COMPLEXITIES OF LINEAR ORDERINGS
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 complexity and show that it only preserves $\Pi ^{\mathrm {in}}_{\alpha }$ complexities. We then take a more direct approach and exhibit linear orderings of all Scott sentence complexities except $\Sigma ^{\mathrm {in}}_{3}$ and $\Sigma ^{\mathrm {in}}_{\lambda +1}$ for $\lambda $ a limit ordinal. We show that the former cannot be the Scott sentence complexity of a linear ordering. In the process we develop new techniques which appear to be helpful to calculate the Scott sentence complexities of structures.- 13 December 2024
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 90 (4) , 1563-1592
SCOTT SENTENCE COMPLEXITIES OF LINEAR ORDERINGS
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 complexity and show that it only preserves $\Pi ^{\mathrm {in}}_{\alpha }$ complexities. We then take a more direct approach and exhibit linear orderings of all Scott sentence complexities except $\Sigma ^{\mathrm {in}}_{3}$ and $\Sigma ^{\mathrm {in}}_{\lambda +1}$ for $\lambda $ a limit ordinal. We show that the former cannot be the Scott sentence complexity of a linear ordering. In the process we develop new techniques which appear to be helpful to calculate the Scott sentence complexities of structures.- 2 July 2024
- Published by Springer Nature
- p. 72-84
Algorithmic Aspects of Left-Orderings of Solvable Baumslag–Solitar Groups via its Dynamical Realization
- 2 July 2024
- Published by Springer Nature
- p. 72-84
Algorithmic Aspects of Left-Orderings of Solvable Baumslag–Solitar Groups via its Dynamical Realization
- 2 July 2024
- Published by Springer Nature
- p. 166-178
Learning Families of Algebraic Structures from Text
- 2 July 2024
- Published by Springer Nature
- p. 166-178
Learning Families of Algebraic Structures from Text
- Open Access
Algorithmic aspects of left-orderings of solvable Baumslag--Solitar groups via its dynamical realization
We answer a question of Calderoni and Clay by showing that the conjugation equivalence relation of left orderings of the Baumslag-Solitar groups $\mathrm{BS}(1,n)$ is hyperfinite for any $n$. Our proof relies on a classification of $\mathrm{BS}(1,n)$'s left-orderings via its one-dimensional dynamical realizations. We furthermore use the effectiveness of the dynamical realizations of $\mathrm{BS}(1,n)$ to study algorithmic properties of the left-orderings on $\mathrm{BS}(1,n)$.Open AccessAlgorithmic aspects of left-orderings of solvable Baumslag--Solitar groups via its dynamical realization
We answer a question of Calderoni and Clay by showing that the conjugation equivalence relation of left orderings of the Baumslag-Solitar groups $\mathrm{BS}(1,n)$ is hyperfinite for any $n$. Our proof relies on a classification of $\mathrm{BS}(1,n)$'s left-orderings via its one-dimensional dynamical realizations. We furthermore use the effectiveness of the dynamical realizations of $\mathrm{BS}(1,n)$ to study algorithmic properties of the left-orderings on $\mathrm{BS}(1,n)$.