Equivalence Relations on Classes of Computable Structures

DOI10.1007/978-3-642-03073-4_21MaRDI QIDQ3576052zbMATH OpenOpenAlexFDO

Authors E. B. Fokina, Sy-David Friedman

Publication date 28 July 2010

Published in Mathematical Theory and Computational Practice (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03073-4_21

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Recommendations

• scientific article; zbMATH DE number 1904842
• Isomorphism relations on computable structures
• Computably enumerable equivalence relations
• On isomorphism classes of computably enumerable equivalence relations
• Equivalence relations in set theory, computation theory, model theory and complexity theory
• Computability theoretic classifications for classes of structures
• On the degree structure of equivalence relations under computable reducibility
• Publication:4863247
• Structurable equivalence relations
• On ^0_1-classification of relations on computable structures

Cites work

• Analytic equivalence relations and bi-embeddability
• Comparing Classes of Finite Structures
• Complete analytic equivalence relations
• Computable structures and the hyperarithmetical hierarchy
• Degree spectra and computable dimensions in algebraic structures
• scientific article; zbMATH DE number 1390024 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• New Directions in Descriptive Set Theory
• The isomorphism problem for classes of computable fields
• The isomorphism problem for computable Abelian _p-groups of bounded length
• The isomorphism problem for torsion-free abelian groups is analytic complete
• Turing computable embeddings

Cited in

(28)

• Computability of distributive lattices
• Positive preorders
• The intersection of the similarity and conjunctivity equivalence classes
• On bounded type-definable equivalence relations
• A trichotomy for a class of equivalence relations
• Degree spectra of structures
• On the degree structure of equivalence relations under computable reducibility
• Classifications of definable subsets
• Graphs realised by r.e. equivalence relations
• Index set of structures with two equivalence relations that are autostable relative to strong constructivizations
• Classes of structures with no intermediate isomorphism problems
• Universal computably enumerable equivalence relations
• ISOMORPHISM ON HYP
• \({\Sigma}^0_1\) and \({\Pi}^0_1\) equivalence structures
• Structural properties for feasibly computable classes of type two
• scientific article; zbMATH DE number 176240 (Why is no real title available?)
• A Friedberg enumeration of equivalence structures
• DEGREE SPECTRA OF ANALYTIC COMPLETE EQUIVALENCE RELATIONS
• Compound Objects Comparators in Application to Similarity Detection and Object Recognition
• PRIORITY ARGUMENTS VIA TRUE STAGES
• Isomorphism relations on computable structures
• Turing computable embeddings of equivalences other than isomorphism
• Classes of structures with universe a subset of \(\omega _{1}\)
• Comparing Classes of Finite Structures
• Agreement reducibility
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR
• \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures
• Reducibilities among equivalence relations induced by recursively enumerable structures

This page was built for publication: Equivalence Relations on Classes of Computable Structures

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