Switch to: Citations

Add references

You must login to add references.
  1. Punctual Categoricity and Universality.Rod Downey, Noam Greenberg, Alexander Melnikov, Keng Meng Ng & Daniel Turetsky - 2020 - Journal of Symbolic Logic 85 (4):1427-1466.
    We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is${\text {PA}}(0')$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is$0''$. We also prove that, with a bit of work, the latter result can be pushed beyond$\Delta ^1_1$, thus showing that punctually categorical structures can possess arbitrarily complex (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Relationships between computability-theoretic properties of problems.Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey & Dan Turetsky - 2022 - Journal of Symbolic Logic 87 (1):47-71.
    A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • 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 (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • 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.
    Download  
     
    Export citation  
     
    Bookmark   6 citations