5 found
Order:
  1.  8
    Reductions Between Types of Numberings.Ian Herbert, Sanjay Jain, Steffen Lempp, Manat Mustafa & Frank Stephan - 2019 - Annals of Pure and Applied Logic 170 (12):102716.
    This paper considers reductions between types of numberings; these reductions preserve the Rogers Semilattice of the numberings reduced and also preserve the number of minimal and positive degrees in their semilattice. It is shown how to use these reductions to simplify some constructions of specific semilattices. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the k-r.e. numberings to the k+1-r.e. numberings; all further reductions are obtained by (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  9
    Classifying equivalence relations in the Ershov hierarchy.Nikolay Bazhenov, Manat Mustafa, Luca San Mauro, Andrea Sorbi & Mars Yamaleev - 2020 - Archive for Mathematical Logic 59 (7-8):835-864.
    Computably enumerable equivalence relations received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility \. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the \ case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by \ on the \ equivalence relations. (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3.  11
    Elementary Theories and Hereditary Undecidability for Semilattices of Numberings.Nikolay Bazhenov, Manat Mustafa & Mars Yamaleev - 2019 - Archive for Mathematical Logic 58 (3-4):485-500.
    A major theme in the study of degree structures of all types has been the question of the decidability or undecidability of their first order theories. This is a natural and fundamental question that is an important goal in the analysis of these structures. In this paper, we study decidability for theories of upper semilattices that arise from the theory of numberings. We use the following approach: given a level of complexity, say \, we consider the upper semilattice \ of (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4.  2
    Rogers Semilattices of Limitwise Monotonic Numberings.Nikolay Bazhenov, Manat Mustafa & Zhansaya Tleuliyeva - 2022 - Mathematical Logic Quarterly 68 (2):213-226.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5.  2
    Approximating Approximate Reasoning: Fuzzy Sets and the Ershov Hierarchy.Nikolay Bazhenov, Manat Mustafa, Sergei Ospichev & Luca San Mauro - 2021 - In Sujata Ghosh & Thomas Icard (eds.), Logic, Rationality, and Interaction: 8th International Workshop, Lori 2021, Xi’an, China, October 16–18, 2021, Proceedings. Springer Verlag. pp. 1-13.
    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 complexity of their defining formulas. The Ershov Hierarchy classifies Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta ^0_2$$\end{document} sets with respect to the number of mistakes that are needed to approximate them. Biacino and Gerla extended the Kleene Hierarchy to the realm of fuzzy sets, whose membership functions range in a complete lattice L. In (...)
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark