20 citations · 54 across the 26 of their papers we have counts for
27 papers
The tolerant learning hierarchy for c.e. sets
Vittorio Cipriani, Martin Ritter, Luca San Mauro
Learning from positive data models a scenario in which a learner receives longer and longer initial segments of an enumeration of an unknown set and repeatedly outputs a conjecture…
Tenability and Weak Semantics: Modeling Non-uniform Defense -- Extended Version
Uri Andrews, Luca San Mauro, John Spoerl
In Dung-style abstract argumentation, various semantics capture notions of acceptability of arguments. The admissibility semantics capture the notion that an argument can be consis…
Isomorphism relations on classes of c.e. algebras
Meng-Che "Turbo" Ho, Martin Ritter, Luca San Mauro
We investigate the complexity of isomorphism relations for classes of finitely generated and n-generated computably enumerable (c.e.) algebras, presented via c.e. presentations --…
On the Complexity of the Grounded Semantics for Infinite Argumentation Frameworks
Uri Andrews, Luca San Mauro
Argumentation frameworks, consisting of arguments and an attack relation representing conflicts, are fundamental for formally studying reasoning under conflicting information. We u…
Complexity in finitary argumentation (extended version)
Uri Andrews, Luca San Mauro
Abstract argumentation frameworks (AFs) provide a formal setting to analyze many forms of reasoning with conflicting information. While the expressiveness of general infinite AFs m…
On statistical learning of graphs
Vittorio Cipriani, Valentino Delle Rose, Luca San Mauro +1
We study PAC and online learnability of hypothesis classes formed by copies of a countably infinite graph G, where each copy is induced by permuting G's vertices. This corresponds…
SCC-recursiveness in infinite argumentation (extended version)
Uri Andrews, Luca San Mauro
Argumentation frameworks (AFs) are a foundational tool in artificial intelligence for modeling structured reasoning and conflict. SCC-recursiveness is a well-known design principle…
Comparing Dialectical Systems: Contradiction and Counterexample in Belief Change (Extended Version)
Uri Andrews, Luca San Mauro
Dialectical systems are a mathematical formalism for modeling an agent updating a knowledge base seeking consistency. Introduced in the 1970s by Roberto Magari, they were originall…
On the learning power of Friedman-Stanley jumps
Vittorio Cipriani, Alberto Marcone, Luca San Mauro
Recently, a surprising connection between algorithmic learning of algebraic structures and descriptive set theory has emerged. Following this line of research, we define the learni…
Classifying different criteria for learning algebraic structures
Nikolay Bazhenov, Vittorio Cipriani, Sanjay Jain +2
In the last years there has been a growing interest in the study of learning problems associated with algebraic structures. The framework we use models the scenario in which a lear…
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…
Classifying word problems of finitely generated algebras via computable reducibility
Valentino Delle Rose, Luca San Mauro, Andrea Sorbi
We contribute to a recent research program which aims at revisiting the study of the complexity of word problems, a major area of research in combinatorial algebra, through the len…
Investigating the computable Friedman-Stanley jump
Uri Andrews, Luca San Mauro
We answer several questions about the computable Friedman-Stanley jump on equivalence relations. This jump, introduced by Clemens, Coskey, and Krakoff, deepens the natural connecti…
Learning algebraic structures with the help of Borel equivalence relations
Nikolay Bazhenov, Vittorio Cipriani, Luca San Mauro
We study algorithmic learning of algebraic structures. In our framework, a learner receives larger and larger pieces of an arbitrary copy of a computable structure and, at each sta…
Punctual equivalence relations and their (punctual) complexity
Nikolay Bazhenov, Keng Meng Ng, Luca San Mauro +1
The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence rela…
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…
A note on the category of equivalence relations
Valentino Delle Rose, Luca San Mauro, Andrea Sorbi
We make some beginning observations about the category of equivalence relations on the set of natural numbers, where a morphism between two equivalence relat…
On the structure of computable reducibility on equivalence relations of natural numbers
Uri Andrews, Daniel Belin, Luca San Mauro
We examine the degree structure of equivalence relations on under computable reducibility. We examine when pairs of degrees have a join. In particular, we show th…
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…
Learning families of algebraic structures from informant
Nikolay Bazhenov, Ekaterina Fokina, Luca San Mauro
We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization…
Limit Learning Equivalence Structures
Ekaterina Fokina, Timo Kötzing, Luca San Mauro
While most research in Gold-style learning focuses on learning formal languages, we consider the identification of computable structures, specifically equivalence structures. In ou…