Zobrazeno 1 - 10
of 402
pro vyhledávání: '"SORBI, ANDREA"'
Answering an open question raised by Cooper, we show that there exist $\Delta^0_2$ sets $D$ and $E$ such that the singleton degree of $E$ is a minimal cover of the singleton degree of $D$. This shows that the $\Sigma^{0}_{2}$ singleton degrees, and t
Externí odkaz:
http://arxiv.org/abs/2412.18991
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 lens of the theory of computably enumerable equivalence relations (ceers)
Externí odkaz:
http://arxiv.org/abs/2305.11563
Publikováno v:
Computability, vol. 11 (2022), no. 3-4, pp. 187-221
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 relations $R$ and $S$ on natural numbers, $R$ is computably reducible to $
Externí odkaz:
http://arxiv.org/abs/2109.04055
We make some beginning observations about the category $\mathbb{E}\mathrm{q}$ of equivalence relations on the set of natural numbers, where a morphism between two equivalence relations $R,S$ is a mapping from the set of $R$-equivalence classes to tha
Externí odkaz:
http://arxiv.org/abs/2105.09604
Autor:
Sorbi, Andrea
Publikováno v:
The Bulletin of Symbolic Logic, 2022 Dec 01. 28(4), 566-606.
Externí odkaz:
https://www.jstor.org/stable/27187036
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), where being realized means to fall in the same reducibility degree (
Externí odkaz:
http://arxiv.org/abs/2006.07977
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 result for the structure comprised of the dark ceers and the structure
Externí odkaz:
http://arxiv.org/abs/1909.09401
A computably enumerable equivalence relation (ceer) $X$ is called self-full if whenever $f$ is a reduction of $X$ to $X$ then the range of $f$ intersects all $X$-equivalence classes. It is known that the infinite self-full ceers properly contain the
Externí odkaz:
http://arxiv.org/abs/1909.09407
Autor:
Andrews, Uri, Sorbi, Andrea
We study effectively inseparable (e.i.) pre-lattices (i.e. structures of the form $L=\langle \omega, \wedge, \lor, 0, 1, \leq_L\rangle$ where $\omega$ denotes the set of natural numbers and the following hold: $\wedge, \lor$ are binary computable ope
Externí odkaz:
http://arxiv.org/abs/1901.06136
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 investigated the expressive and computational power of dialectical systems
Externí odkaz:
http://arxiv.org/abs/1810.07103