scientific article; zbMATH DE number 4160710

MaRDI QIDQ3487329zbMATH OpenFDO

Authors S. Barry Cooper

Publication date 1990

zbMATH Keywords

enumeration degreesTuring reducibilityenumeration reducibility

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• Enumeration reducibility and computable structure theory
• On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
• Computably enumerable sets and quasi-reducibility
• On reducibility of partial recursive functions
• On \(p\)-reducibility of computable numerations
• scientific article; zbMATH DE number 7649961
• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• Enumerations in computable structure theory
• Logical Approaches to Computational Barriers
• DEFINABILITY OF RECURSIVELY ENUMERABLE SETS IN ABSTRACT COMPUTATIONAL COMPLEXITY THEORY

Cited in

(40)

• The Turing universe in the context of enumeration reducibility
• Strong Reducibilities of Enumerations and Partial Enumerated Algebras
• Complements for enumeration \(\Pi_1^0\)-degrees
• Total Degrees and Nonsplitting Properties of $\Sigma_2^0$ Enumeration Degrees
• The minimal e-degree problem in fragments of Peano arithmetic
• A note on the enumeration degrees of 1-generic sets
• Avoiding uniformity in the \(\Delta_2^0\) enumeration degrees
• Cupping and noncupping in the enumeration degrees of \(\Sigma_ 2^ 0\) sets
• Enumeration reducibility and positive reducibility of the numberings of families of arithmetic sets
• Strong minimal pairs in the enumeration degrees
• Fragments of the theory of the enumeration degrees
• Agreement reducibility
• scientific article; zbMATH DE number 4094815 (Why is no real title available?)
• The automorphism group and definability of the jump operator in the \(\omega\)-enumeration degrees
• The automorphism group of the enumeration degrees
• Sets of generator and automorphism bases for the enumeration degrees
• On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
• Enumeration reducibility and computable structure theory
• scientific article; zbMATH DE number 1531937 (Why is no real title available?)
• The enumeration degrees: local and global structural interactions
• Splitting and nonsplitting in the \(\Sigma_2^0\) enumeration degrees
• Definability via Kalimullin pairs in the structure of the enumeration degrees
• Empty intervals in the enumeration degrees
• The high/low hierarchy in the local structure of the \(\omega\)-enumeration degrees
• The jump operator on the \(\omega \)-enumeration degrees
• There exists a maximal 3-c.e. enumeration degree
• The complexity space of partial functions: a connection between complexity analysis and denotational semantics
• Enumeration Reducibility Using Bounded Information: Counting Minimal Covers
• Cupping Classes of $\Sigma^0_2$ Enumeration Degrees
• IN MEMORIAM: BARRY COOPER 1943–2015
• s-Degrees within e-Degrees
• Weakly semirecursive sets and r.e. orderings
• Density of the cototal enumeration degrees
• scientific article; zbMATH DE number 3960995 (Why is no real title available?)
• Cupping and definability in the local structure of the enumeration degrees
• scientific article; zbMATH DE number 7360060 (Why is no real title available?)
• Branching in the enumeration degrees of the \(\Sigma_2^0\) sets
• The structure of the s-degrees contained within a single e-degree
• The jump operation for structure degrees
• On \(p\)-reducibility of computable numerations

This page was built for publication:

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