Enumeration reducibility and computable structure theory

DOI10.1007/978-3-319-50062-1_19zbMATH Open1485.03118OpenAlexW2559125440MaRDI QIDQ2970965FDOQ2970965

Authors: Alexandra Soskova, Mariya I. Soskova 

Publication date: 4 April 2017

Published in: Computability and Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-50062-1_19

Recommendations

• scientific article
• scientific article; zbMATH DE number 1531937
• On computably enumerable structures
• scientific article; zbMATH DE number 871851
• Computability-Theoretic Complexity of Countable Structures

zbMATH Keywords

degree spectraenumeration reducibilityenumeration jump

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Other degrees and reducibilities in computability and recursion theory (03D30)

Cites Work

• Elementary induction on abstract structures
• HF-computability
• Generic copies of countable structures
• Computable structures and the hyperarithmetical hierarchy
• Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ₂ sets are dense
• Enumeration reducibility and partial degrees
• Effective model theory vs. recursive model theory
• Semirecursive Sets and Positive Reducibility
• Title not available (Why is that?)
• Enumerations in computable structure theory
• A jump inversion theorem for the enumeration jump
• Jumps of quasi-minimal enumeration degrees
• Reducibility and Completeness for Sets of Integers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Interpreting true arithmetic in the local structure of the enumeration degrees
• A Jump Inversion Theorem for the Degree Spectra
• Arithmetical Reducibilities I
• Definability via enumerations
• Definability in the local theory of the \(\omega \)-enumeration degrees
• Rice sequences of relations
• Non Σ_n axiomatizable almost strongly minimal theories
• Degrees coded in jumps of orderings
• Title not available (Why is that?)
• Degrees of Structures
• Complexity of Categorical Theories with Computable Models
• Metarecursive sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Relative to any nonrecursive set
• Enumerations, countable structures and Turing degrees
• Computability by means of effectively definable schemes and definability via enumerations
• Abstract First Order Computability. I
• Abstract Computability and Invariant Definability
• On the $n$-back-and-forth types of Boolean algebras
• Notes on the Jump of a Structure
• Title not available (Why is that?)
• Title not available (Why is that?)
• A jump inversion theorem for the semilattices of \(\Sigma\)-degrees
• A Jump Inversion Theorem for the Degree Spectra
• Some Notes on Degree Spectra of the Structures
• Every Set has a Least Jump Enumeration
• Title not available (Why is that?)
• The jump operator on the \(\omega \)-enumeration degrees
• Embedding countable partial orderings in the enumeration degrees and the \(\omega \)-enumeration degrees
• Note on Degrees of Partial Functions
• Exact Pair Theorem for the ω-Enumeration Degrees
• The  -Enumeration Degrees
• The high/low hierarchy in the local structure of the \(\omega\)-enumeration degrees
• Relative to any non-hyperarithmetic set
• Generalizations of enumeration reducibility using recursive infinitary propositional sentences
• Title not available (Why is that?)
• The jump operation for structure degrees
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Note on ω-Jump Inversion of Degree Spectra of Structures
• Enumeration Degrees and Enumerability of Familes
• Uniform regular enumerations
• A note on the hyperarithmetical hierarchy
• Regular enumerations
• Ash's theorem for abstract structures
• Quasi-minimal enumeration degrees and minimal Turing degrees
• Definability via Kalimullin pairs in the structure of the enumeration degrees
• Defining totality in the enumeration degrees
• New Computational Paradigms
• Another jump inversion theorem for structures
• ON EXTENSIONS OF EMBEDDINGS INTO THE ENUMERATION DEGREES OF THE ${\Sigma_2^0}$-SETS
• Relativized Degree Spectra
• Logical Approaches to Computational Barriers
• A computable ℵ₀-categorical structure whose theory computes true arithmetic
• Title not available (Why is that?)
• Constructing minimal pairs of degrees
• Effective properties of Marker's extensions
• Title not available (Why is that?)
• Conservative extensions of abstract structures
• ω-Degree Spectra
• Title not available (Why is that?)
• Quasi-minimal degrees for degree spectra
• Title not available (Why is that?)

Cited In (17)

• Coding and definability in computable structures
• Computable fields and the bounded Turing reduction
• Title not available (Why is that?)
• Dense computability, upper cones, and minimal pairs
• On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
• Title not available (Why is that?)
• \(Q\)-reducibility and \(m\)-reducibility on computably enumerable sets
• Computability-Theoretic Complexity of Countable Structures
• Title not available (Why is that?)
• Computably enumerable sets and quasi-reducibility
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR
• On computably enumerable structures
• On functors enumerating structures
• Positive enumerable functors
• Bounded enumeration reducibility and its degree structure
• On \(p\)-reducibility of computable numerations
• The Turing universe in the context of enumeration reducibility

This page was built for publication: Enumeration reducibility and computable structure theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970965)