Search

Partiality is a natural phenomenon in computability that we cannot get around. So, the question is whether we can give the areas where partiality occurs, that is, where non-termination happens, more structure. In this paper we consider function classes which besides the total functions only contain finite functions whose domain of definition is an initial segment of the natural numbers. Such functions appear naturally in computation. We show that a rich computability theory can be developed for these functions classes which embraces the central results of classical computability theory, in which all partial (computable) functions are considered. To do so, the concept of a Gödel number is generalised, resulting in a broader class of numberings. The central algorithmic idea in this approach is to search in enumerated lists. In this way, function computability is reduced to set listability. Besides the development of a computability theory for the functions classes, the new numberings – called quasi-Gödel numberings – are studied from a numbering-theoretic perspective: they are complete, and each of the function classes numbered in this way is a retract of the Gödel numbered set of all partial computable functions. Moreover, the Rogers semi-lattice of all computable numberings of the considered function classes is studied and results as in the case of the computable numberings of the partial computable functions are obtained. The function classes are shown to be effectively given algebraic domains in the sense of Scott–Ershov. The quasi-Gödel numberings are exactly the admissible numberings of the computable elements of the domain. Moreover, the domain can be computably mapped onto every other effectively given one so that every admissible numbering of the computable domain elements is generated by a quasi-Gödel numbering via this mapping. [ABSTRACT FROM AUTHOR]

The concept of a tolerance relation, shortly called tolerance, was studied on various algebras since the seventies of the twentieth century by B. Zelinka and the first author (see e.g. [6] and the monograph [1] and the references therein). Since tolerances need not be transitive, their blocks may overlap and hence in general the set of all blocks of a tolerance cannot be converted into a quotient algebra in the same way as in the case of congruences. However, G. Czédli ([7]) showed that lattices can be factorized by means of tolerances in a natural way, and J. Grygiel and S. Radeleczki ([8]) proved some variant of an Isomorphism Theorem for tolerances on lattices. The aim of the present paper is to extend the concept of a tolerance on a lattice to posets in such a way that results similar to those obtained for tolerances on lattices can be derived. [ABSTRACT FROM AUTHOR]

Let T(X) be the full transformation semigroup on the set X . For a fixed nonempty subset Y of X, let PGY (X) = {α ∈ T(X) : α|Y ∈ G(Y )} where G(Y ) is the permutation group on Y . It is known that P GY (X) is a regular subsemigroup of T(X). In this paper, we give a simpler description of Green’s relations and characterize the ideals of P GY (X). Moreover, we prove some isomorphism theorems for PGY (X). For finite sets, we investigate the cardinalities of PGY (X) and of its subsets of idempotents, and we also calculate their ranks. [ABSTRACT FROM AUTHOR]

Let R be a Krasner hyperring. In this paper, we prove a factorization theorem in the category of Krasner R-hypermodules with inclusion single-valued R-homomorphisms as its morphisms. Then, we prove various isomorphism theorems for a smaller category, i.e., the category of Krasner R-hypermodules with strong single-valued R-homomorphisms as its morphisms. In addition, we show that the latter category is balanced. Finally, we prove that for every strong single-valued R-homomorphism f : A → B and a ∈ A , we have K e r (f) + a = a + K e r (f) = { x ∈ A ∣ f (x) = f (a) } . [ABSTRACT FROM AUTHOR]