7 citations · 22 across the 9 of their papers we have counts for
11 papers
Dichotomy results for classes of countable graphs
Vittorio Cipriani, Ekaterina Fokina, Matthew Harrison-Trainor +2
We study classes of countable graphs where every member does not contain a given finite graph as an induced subgraph -- denoted by for a given finite g…
Uniformity in learning structures
Vittorio Cipriani, Dino Rossegger
The standard framework for studying learning problems on algebraic structures assumes that the structures in the target family are pairwise nonisomorphic. Under this assumption, th…
Feferman's completeness theorem
Fedor Pakhomov, Michael Rathjen, Dino Rossegger
Feferman proved in 1962 that any arithmetical theorem is a consequence of a suitable transfinite iteration of full uniform reflection of . This result is commonly know…
Learning Families of Algebraic Structures from Text
Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger +2
We adapt the classical notion of learning from text to computable structure theory. Our main result is a model-theoretic characterization of the learnability from text for classes…
A Lopez-Escobar Theorem for Continuous Domains
Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger +2
We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let be the set of countable structures with universe in vocabulary topologized b…
Degree spectra of analytic complete equivalence relations
Dino Rossegger
We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by this relations. We first gi…
On bi-embeddable categoricity of algebraic structures
Nikolay Bazhenov, Dino Rossegger, Maxim Zubkov
In several classes of countable structures it is known that every hyperarithmetic structure has a computable presentation up to bi-embeddability. In this article we investigate the…
Degrees of bi-embeddable categoricity
Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger +1
We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure…
Bi-embeddability spectra and bases of spectra
Ekaterina Fokina, Dino Rossegger, Luca San Mauro
We study degree spectra of structures with respect to the bi-embeddability relation. The bi-embeddability spectrum of a structure is the family of Turing degrees of its bi-embeddab…
Measuring the complexity of reductions between equivalence relations
Ekaterina Fokina, Dino Rossegger, Luca San Mauro
Computable reducibility is a well-established notion that allows to compare the complexity of various equivalence relations over the natural numbers. We generalize computable reduc…
Degrees of bi-embeddable categoricity of equivalence structures
Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger +1
We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) b…