Abstract In this article, we define and study the notion of a $(c,c_{1})$-cylinder, which turns out to be very useful instrument for investigating the relationships between conjunctive reducibility ($c$-reducibility) and its injective version $c_{1}$-reducibility. Using this notion, we prove the following results: (i) Neither hypersimple sets nor hemimaximal sets can be $(c,c_{1})$-cylinders; (ii) The $c$-degree of a noncomputable c.e. set contains either only one or infinitely many noncomputable $c_{1}$-degrees; (iii) the $c$-degree of either a hemimaximal set or a hypersimple set contains infinitely many noncomputable $c_{1}$-degrees.

Artificial Intelligence is developing using statistical and logical approaches. Considerable efforts have been devoted to combining logical and probabilistic methods in a single framework, which influenced the development of several formalisms and programming tools. Such formalisms allow representation and reasoning about uncertain knowledge. Uncertainty happens in many areas, like medicine, manufacturing, weather forecasts, prediction (of e.g. voting intentions, natural disaster), etc. Ontologies are machine-processable formalisms for knowledge representation. Their purpose is to describe objects according to domain of interests. This knowledge is used by (automated) reasoning systems for query answering. Probabilistic ontologies are obtained by adding a probabilistic interpretation to the constraints forming the ontology, and adapting corresponding reasoning methods to handle these probabilities. The RFEPO is an interdisciplinary project and aims at formulating unification and matching problems used in probabilistic ontology reasoning, and to search and compare algorithms for their solution. Additionally, when there is no algorithm for solving them, our project aims to study the algebraic structures of degrees induced by Turing and other algorithmic reducibilities.

Abstract In this article we prove the following results: (i) Every hemimaximal set has minimal $c_{1}$-degree, i.e. if $B$ is hemimaximal and $A$ is a c.e. set such that $A \le _{c_{1}} B$ then either $B \leq _{{c}_{1}} A$ or $A$ is computable. (ii) The $sQ$-degree of a c.e. set contains either only one or infinitely many c.e. $c$-degrees. (iii) If $A,B$ are c.e. cylinders in the same $sQ_{1}$-degree and $A<_{c_{1}} B$, then this $sQ_{1}$-degree contains infinitely many c.e. $c_{1}$-degrees.

We study the relationship between weak truth-table (⁠|$wtt$|⁠)-degrees and |$Q$|-degrees and give some completeness criteria of |$wtt$|- and bounded weak truth-table (⁠|$bwtt$|⁠)-reducibilities. We prove that every noncomputable computably enumerable (c.e.) |$wtt$|-degree contains a c.e. set |$A$| such that the |$Q$|-degree of |$A$| contains neither simple nor nowhere simple sets. We show that every noncomputable c.e. |$bwtt$|-degree contains an infinite antichain of noncomputable c.e. |$bsQ$|-degrees.

Abstract Let A be an infinite set and let K be creative: we show that K ≤QA if and only if K A. (Here ≤Q denotes Q-reducibility, and is the subreducibility of ≤Q obtained by requesting that Q-reducibility be provided by a computable function f such that Wf(x) ∩ Wf(y) = ∅. if x ≠ y.) Using this result we prove that A is hyperhyperimmune if and only if no subset B of A is s-complete, i.e., there is no subset B of A such that ≤sB, where ≤s denotes s-reducibility, and denotes the complement of K.

Abstract We prove that a computably enumerable set A is effectively speedable (effectively levelable) if and only if there exists a splitting (A0, A1) of A such that both A0 and A1 are effectively speedable (effectively levelable). These results answer two questions raised by J. B. Remmel.