7 citations · 19 across the 14 of their papers we have counts for
18 papers
Conjunctive reducibilities and completeness
Irakli Chitaia, Keng Meng Ng, Roland Omanadze +1
In this article we study the notion of completeness for conjunctive reducibilities. We investigate the relationship between -completeness and -completeness of computably enum…
Intuitionism and computing with partial information
Hristo Ganchev, Paul Shafer, Theodore A. Slaman +2
There exist initial segments of both the Dyment lattice and the Dyment-Muchnik lattice that yield Brouwer algebras modeling exactly the intuitionistic propositional calculus. For t…
The singleton degrees of the sets are not dense
Thomas F. Kent, Keng Meng Ng, Andrea Sorbi
Answering an open question raised by Cooper, we show that there exist sets and such that the singleton degree of is a minimal cover of the singleton degree of $…
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…
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…
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…
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)…
Self-full ceers and the uniform join operator
Uri Andrews, Noah Schweber, Andrea Sorbi
A computably enumerable equivalence relation (ceer) is called self-full if whenever is a reduction of to then the range of intersects all -equivalence classe…
The Theory of Ceers Computes True Arithmetic
Uri Andrews, Noah Schweber, Andrea Sorbi
We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same…
Effective inseparability, lattices, and pre-ordering relations
Uri Andrews, Andrea Sorbi
We study effectively inseparable (e.i.) pre-lattices (i.e. structures of the form where denotes the set of natural numbers and…
Trial and error mathematics: Dialectical systems and completions of theories
Jacopo Amidei, Uri Andrews, Duccio Pianigiani +2
This paper is part of a project that is based on the notion of dialectical system, introduced by Magari as a way of capturing trial and error mathematics. In previous work, we inve…
Classifying equivalence relations in the Ershov hierarchy
Nikolay Bazhenov, Manat Mustafa, Luca San Mauro +2
Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility $\…
Comparing the degrees of enumerability and the closed Medvedev degrees
Paul Shafer, Andrea Sorbi
We compare the degrees of enumerability and the closed Medvedev degrees and find that many situations occur. There are nonzero closed degrees that do not bound nonzero degrees of e…
Joins and meets in the structure of Ceers
Uri Andrews, Andrea Sorbi
We study computably enumerable equivalence relations (abbreviated as ceers) under computable reducibility, and we investigate the resulting degree structure Ceers, which is a poset…
Calibrating word problems of groups via the complexity of equivalence relations
André Nies, Andrea Sorbi
(1) There is a finitely presented group with a word problem which is a uniformly effectively inseparable equivalence relation. (2) There is a finitely generated group of computable…
Generalizations of the Weak Law of the Excluded Middle
Andrea Sorbi, Sebastiaan A. Terwijn
We study a class of formulas generalizing the weak law of the excluded middle, and provide a characterization of these formulas in terms of Kripke frames and Brouwer algebras. We u…
Intuitionistic Logic and Muchnik Degrees
Andrea Sorbi, Sebastiaan A. Terwijn
We prove that there is a factor of the Muchnik lattice that captures intuitionistic propositional logic. This complements a now classic result of Skvortsova for the Medvedev lattic…
Intermediate logics and factors of the Medvedev lattice
Andrea Sorbi, Sebastiaan A. Terwijn
We investigate the initial segments of the Medvedev lattice as Brouwer algebras, and study the propositional logics connected to them.