6 citations · 6 across the 9 of their papers we have counts for
11 papers · 1 filter
Analogues of the countable Borel equivalence relations in the setting of computable reducibility
Uri Andrews, Luca San Mauro
Coskey, Hamkins, and Miller [CHM12] proposed two possible analogues of the class of countable Borel equivalence relations in the setting of computable reducibility of equivalence r…
Approximating approximate reasoning: Fuzzy sets and the Ershov hierarchy
Nikolay Bazhenov, Manat Mustafa, Sergei Ospichev +1
Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order…
On the Turing complexity of learning finite families of algebraic structures
Nikolay Bazhenov, Luca San Mauro
In previous work, we have combined computable structure theory and algorithmic learning theory to study which families of algebraic structures are learnable in the limit (up to iso…
Word problems and ceers
Valentino Delle Rose, Luca San Mauro, Andrea Sorbi
This note addresses the issue as to which ceers can be realized by word problems of computably enumerable (or, simply, c.e.) structures (such as c.e. semigroups, groups, and rings)…
Comparing the isomorphism types of equivalence structures and preorders
Nikolay Bazhenov, Luca San Mauro
A general theme of computable structure theory is to investigate when structures have copies of a given complexity . We discuss such problem for the case of equivalence structur…
Minimal Equivalence Relations in Hyperarithmetical and Analytical Hierarchies
Nikolay Bazhenov, Manat Mustafa, Luca San Mauro +1
A standard tool for classifying the complexity of equivalence relations on is provided by computable reducibility. This reducibility gives rise to a rich degree structure. The…