15 found
Order:
Disambiguations
Iskander Kalimullin [8]Iskander Sh Kalimullin [8]Iskander S. Kalimullin [1]
  1.  33
    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   8 citations  
  2.  95
    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   19 citations  
  3.  24
    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   5 citations  
  4.  38
    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.  39
    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   4 citations  
  6.  29
    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   2 citations  
  7.  34
    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  
  8.  15
    (1 other version)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   1 citation  
  9.  24
    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.
    It is proved that for every countable structure and a computable successor ordinal α there is a countable structure which is ‐least among all countable structures such that is Σ‐definable in the αth jump. We also show that this result does not hold for the limit ordinal. Moreover, we prove that there is no countable structure with the degree spectrum for.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  57
    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  
  11.  15
    Limitwise monotonic sets of reals.Marat Faizrahmanov & Iskander Kalimullin - 2015 - Mathematical Logic Quarterly 61 (3):224-229.
    We extend the limitwise monotonicity notion to the case of arbitrary computable linear ordering to get a set which is limitwise monotonic precisely in the non‐computable degrees. Also we get a series of connected non‐uniformity results to obtain new examples of non‐uniformly equivalent families of computable sets with the same enumeration degree spectrum.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  34
    Pa Relative to an Enumeration Oracle.G. O. H. Jun Le, Iskander Sh Kalimullin, Joseph S. Miller & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (4):1497-1525.
    Recall that B is PA relative to A if B computes a member of every nonempty $\Pi ^0_1(A)$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $\Pi ^0_1$ class relative to an enumeration oracle A, which they called a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We study the induced extension of the relation B is PA relative (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  13.  29
    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  
  14.  20
    The enumeration spectrum hierarchy of n‐families.Marat Faizrahmanov & Iskander Kalimullin - 2016 - Mathematical Logic Quarterly 62 (4-5):420-426.
    We introduce a hierarchy of sets which can be derived from the integers using countable collections. Such families can be coded into countable algebraic structures preserving their algorithmic properties. We prove that for different finite levels of the hierarchy the corresponding algebraic structures have different classes of possible degree spectra.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  13
    On Cupping and Ahmad Pairs.Iskander Sh Kalimullin, Steffen Lempp, N. G. Keng Meng & Mars M. Yamaleev - forthcoming - Journal of Symbolic Logic:1-12.
    Working toward showing the decidability of the $\forall \exists $ -theory of the ${\Sigma ^0_2}$ -enumeration degrees, we prove that no so-called Ahmad pair of ${\Sigma ^0_2}$ -enumeration degrees can join to ${\mathbf 0}_e'$.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark