14 found
Order:
Disambiguations
Iskander Kalimullin [8]Iskander Sh Kalimullin [6]Iskander S. Kalimullin [1]
  1.  53
    Degrees of Categoricity of Computable Structures.Ekaterina B. Fokina, Iskander Kalimullin & Russell Miller - 2010 - Archive for Mathematical Logic 49 (1):51-67.
    Defining the degree of categoricity of a computable structure ${\mathcal{M}}$ to be the least degree d for which ${\mathcal{M}}$ is d-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that for all n, degrees d.c.e. in and above 0 (n) can be so realized, as can the degree 0 (ω).
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  2.  15
    Foundations of Online Structure Theory.Nikolay Bazhenov, Rod Downey, Iskander Kalimullin & Alexander Melnikov - 2019 - Bulletin of Symbolic Logic 25 (2):141-181.
    The survey contains a detailed discussion of methods and results in the new emerging area of online “punctual” structure theory. We also state several open problems.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  3.  14
    Automatic and Polynomial-Time Algebraic Structures.Nikolay Bazhenov, Matthew Harrison-Trainor, Iskander Kalimullin, Alexander Melnikov & Keng Meng Ng - 2019 - Journal of Symbolic Logic 84 (4):1630-1669.
    A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  4.  14
    Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.
    For a computable structure $\mathcal {M}$, the categoricity spectrum is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable copies of $\mathcal {M}$. If the spectrum has a least degree, this degree is called the degree of categoricity of $\mathcal {M}$. In this paper we investigate spectra of categoricity for computable rigid structures. In particular, we give examples of rigid structures without degrees of categoricity.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  5.  19
    Degrees of Categoricity and Spectral Dimension.Nikolay A. Bazhenov, Iskander Sh Kalimullin & Mars M. Yamaleev - 2018 - Journal of Symbolic Logic 83 (1):103-116.
    A Turing degreedis the degree of categoricity of a computable structure${\cal S}$ifdis the least degree capable of computing isomorphisms among arbitrary computable copies of${\cal S}$. A degreedis the strong degree of categoricity of${\cal S}$ifdis the degree of categoricity of${\cal S}$, and there are computable copies${\cal A}$and${\cal B}$of${\cal S}$such that every isomorphism from${\cal A}$onto${\cal B}$computesd. In this paper, we build a c.e. degreedand a computable rigid structure${\cal M}$such thatdis the degree of categoricity of${\cal M}$, butdis not the strong degree of categoricity (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  6.  21
    Degree Spectra and Immunity Properties.Barbara F. Csima & Iskander S. Kalimullin - 2010 - Mathematical Logic Quarterly 56 (1):67-77.
    We analyze the degree spectra of structures in which different types of immunity conditions are encoded. In particular, we give an example of a structure whose degree spectrum coincides with the hyperimmune degrees. As a corollary, this shows the existence of an almost computable structure of which the complement of the degree spectrum is uncountable.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  7.  8
    Jump Inversions of Algebraic Structures and Σ‐Definability.Marat Faizrahmanov, Asher Kach, Iskander Kalimullin, Antonio Montalbán & Vadim Puzarenko - 2019 - Mathematical Logic Quarterly 65 (1):37-45.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  38
    Density Results in the Δ 2 0 E-Degrees.Marat M. Arslanov, Iskander Sh Kalimullin & Andrea Sorbi - 2001 - Archive for Mathematical Logic 40 (8):597-614.
    We show that the Δ0 2 enumeration degrees are dense. We also show that for every nonzero n-c. e. e-degree a, with n≥ 3, one can always find a nonzero 3-c. e. e-degree b such that b < a on the other hand there is a nonzero ωc. e. e-degree which bounds no nonzero n-c. e. e-degree.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  9.  10
    Punctual Definability on Structures.Iskander Kalimullin, Alexander Melnikov & Antonio Montalban - 2021 - Annals of Pure and Applied Logic 172 (8):102987.
    We study punctual categoricity on a cone and intrinsically punctual functions and obtain complete structural characterizations in terms of model-theoretic notions. As a corollary, we answer a question of Bazhenov, Downey, Kalimullin, and Melnikov by showing that relational structures are not punctually universal. We will also apply this characterisation to derive an algebraic characterisation of relatively punctually categorical mono-unary structures.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  1
    A Structural Dichotomy in the Enumeration Degrees.Hristo A. Ganchev, Iskander Sh Kalimullin, Joseph S. Miller & Mariya I. Soskova - 2022 - Journal of Symbolic Logic 87 (2):527-544.
    We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half of a nontrivial relativized $\mathcal {K}$ -pair. This leads to a structural dichotomy in the enumeration degrees.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11.  4
    A Structural Dichotomy in the Enumeration Degrees.Hristo A. Ganchev, Iskander Sh Kalimullin, Joseph S. Miller & Mariya I. Soskova - 2020 - Journal of Symbolic Logic:1-18.
    We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half a nontrivial relativized K-pair. This leads to a structural dichotomy in the enumeration degrees.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  3
    On Downey's Conjecture.Marat M. Arslanov, Iskander Sh Kalimullin & Steffen Lempp - 2010 - Journal of Symbolic Logic 75 (2):401-441.
    We prove that the degree structures of the d.c.e. and the 3-c.e. Turing degrees are not elementarily equivalent, thus refuting a conjecture of Downey. More specifically, we show that the following statement fails in the former but holds in the latter structure: There are degrees f > e > d > 0 such that any degree u ≤ f is either comparable with both e and d, or incomparable with both.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  4
    Limitwise Monotonic Sets of Reals.Marat Faizrahmanov & Iskander Kalimullin - 2015 - Mathematical Logic Quarterly 61 (3):224-229.
    Direct download  
     
    Export citation  
     
    Bookmark  
  14.  1
    The Enumeration Spectrum Hierarchy Ofn-Families.Marat Faizrahmanov & Iskander Kalimullin - 2016 - Mathematical Logic Quarterly 62 (4-5):420-426.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark