9 found
Order:
  1.  23
    Degrees of bi-embeddable categoricity of equivalence structures.Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger & Luca San Mauro - 2019 - Archive for Mathematical Logic 58 (5-6):543-563.
    We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, \ bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of \ bi-embeddable categoricity and relative \ bi-embeddable categoricity coincide for equivalence structures for \. We also prove that computable equivalence structures have degree of bi-embeddable categoricity \, or \. We furthermore obtain results (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  2.  11
    The complexity of Scott sentences of scattered linear orders.Rachael Alvir & Dino Rossegger - 2020 - Journal of Symbolic Logic 85 (3):1079-1101.
    We calculate the complexity of Scott sentences of scattered linear orders. Given a countable scattered linear order L of Hausdorff rank $\alpha $ we show that it has a ${d\text {-}\Sigma _{2\alpha +1}}$ Scott sentence. It follows from results of Ash [2] that for every countable $\alpha $ there is a linear order whose optimal Scott sentence has this complexity. Therefore, our bounds are tight. We furthermore show that every Hausdorff rank 1 linear order has an optimal ${\Pi ^{\mathrm {c}}_{3}}$ (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3. Degrees of bi-embeddable categoricity.Luca San Mauro, Nikolay Bazhenov, Ekaterina Fokina & Dino Rossegger - 2021 - Computability 1 (10):1-16.
    We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure A as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of A; the degree of bi-embeddable categoricity of A is the least degree in this spectrum (if it exists). We extend many known results about categoricity spectra to the case of bi-embeddability. In particular, we exhibit structures without degree of bi-embeddable categoricity, and (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  3
    Bi‐embeddability spectra and bases of spectra.Ekaterina Fokina, Dino Rossegger & Luca San Mauro - 2019 - Mathematical Logic Quarterly 65 (2):228-236.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  5. Computable bi-embeddable categoricity.Luca San Mauro, Nikolay Bazhenov, Ekaterina Fokina & Dino Rossegger - 2018 - Algebra and Logic 5 (57):392-396.
    We study the algorithmic complexity of isomorphic embeddings between computable structures.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6. Bi-embeddability spectra and basis of spectra.Luca San Mauro, Ekaterina Fokina & Dino Rossegger - 2019 - Mathematical Logic Quarterly 2 (65):228-236.
    We study degree spectra of structures with respect to the bi-embeddability relation. The bi-embeddability spectrum of a structure is the family of Turing degrees of its bi-embeddable copies. To facilitate our study we introduce the notions of bi-embeddable triviality and basis of a spectrum. Using bi-embeddable triviality we show that several known families of degrees are bi-embeddability spectra of structures. We then characterize the bi-embeddability spectra of linear orderings and study bases of bi-embeddability spectra of strongly locally finite graphs.
     
    Export citation  
     
    Bookmark  
  7. Measuring the complexity of reductions between equivalence relations.Luca San Mauro, Ekaterina Fokina & Dino Rossegger - 2019 - Computability 3 (8):265-280.
    Computable reducibility is a well-established notion that allows to compare the complexity of various equivalence relations over the natural numbers. We generalize computable reducibility by introducing degree spectra of reducibility and bi-reducibility. These spectra provide a natural way of measuring the complexity of reductions between equivalence relations. We prove that any upward closed collection of Turing degrees with a countable basis can be realised as a reducibility spectrum or as a bi-reducibility spectrum. We show also that there is a reducibility (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  8.  3
    On bi-embeddable categoricity of algebraic structures.Nikolay Bazhenov, Dino Rossegger & Maxim Zubkov - 2022 - Annals of Pure and Applied Logic 173 (3):103060.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9. Degree Spectra of Analytic Complete Equivalence Relations.Dino Rossegger - 2022 - Journal of Symbolic Logic 87 (4):1663-1676.
    We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by these relations. We first give a Borel reduction from embeddability on graphs to elementary embeddability on graphs. As a consequence we obtain that elementary bi-embeddability on graphs is a $\boldsymbol {\Sigma }^1_1$ complete equivalence relation. We then investigate the algorithmic properties of this reduction. We obtain that elementary bi-embeddability on the class of computable graphs is $\Sigma ^1_1$ complete with respect (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark