Journal of Symbolic Logic · 2012 · 73 citations · 20 references
ComputingComputer ScienceMathematicsAlgebraSet TheoryTheory Of ComputationAxiomatic Set TheoryComplexity TheoryComputability TheoryComputational ComplexityComputational Complexity ClassesStructural ComplexityComputable ReducibilityComputable Structure TheoryHyperarithmetic HierarchyReducibilityStructural Properties Of Complexity ClassesTuring Reducibility
Abstract We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF -reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all equivalence relations on hyperarithmetical subsets of ω .
20
Theory of Recursive Functions and Effective Computability
D. C. Cooper · The Computer Journal · 1969 · 2.6K citations · Full text
Recursive pseudo-well-orderings
Transactions of the American Mathematical Society · 1968 · 119 citations · Full text
Computable Structure and Non-Structure Theorems
Julia F. Knight · Algebra and Logic · 2002 · 109 citations