Isomorphism relations on computable structures

, , , , &
Journal of Symbolic Logic 77 (1):122-132 (2012)
  Copy   BIBTEX

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 ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1327068695

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 103,703

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

On Σ1 1 equivalence relations over the natural numbers.Ekaterina B. Fokina & Sy-David Friedman - 2012 - Mathematical Logic Quarterly 58 (1-2):113-124.
Isomorphism of Homogeneous Structures.John D. Clemens - 2009 - Notre Dame Journal of Formal Logic 50 (1):1-22.
On the isomorphism problem for some classes of computable algebraic structures.Valentina S. Harizanov, Steffen Lempp, Charles F. D. McCoy, Andrei S. Morozov & Reed Solomon - 2022 - Archive for Mathematical Logic 61 (5):813-825.
The isomorphism problem for computable Abelian p-groups of bounded length.Wesley Calvert - 2005 - Journal of Symbolic Logic 70 (1):331-345.
The Isomorphism Problem for Computable Abelian p-Groups of Bounded Length.Wesley Calvert - 2005 - Journal of Symbolic Logic 70 (1):331 - 345.
Partial automorphism semigroups.Jennifer Chubb, Valentina S. Harizanov, Andrei S. Morozov, Sarah Pingrey & Eric Ufferman - 2008 - Annals of Pure and Applied Logic 156 (2):245-258.
Isomorphism of Locally Compact Polish Metric Structures.Maciej Malicki - 2024 - Journal of Symbolic Logic 89 (2):646-664.
Investigating the Computable Friedman–Stanley Jump.Uri Andrews & Luca San Mauro - 2024 - Journal of Symbolic Logic 89 (2):918-944.
On isomorphism classes of computably enumerable equivalence relations.Uri Andrews & Serikzhan A. Badaev - 2020 - Journal of Symbolic Logic 85 (1):61-86.
Analytic equivalence relations and bi-embeddability.Sy-David Friedman & Luca Motto Ros - 2011 - Journal of Symbolic Logic 76 (1):243 - 266.

Analytics

Added to PP
2012-01-21

Downloads
78 (#283,935)

6 months
6 (#683,963)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Valentina Harizanov
George Washington University
Sy-David Friedman

Citations of this work

Computable Abelian groups.Alexander G. Melnikov - 2014 - Bulletin of Symbolic Logic 20 (3):315-356,.
The theory of ceers computes true arithmetic.Uri Andrews, Noah Schweber & Andrea Sorbi - 2020 - Annals of Pure and Applied Logic 171 (8):102811.
Jumps of computably enumerable equivalence relations.Uri Andrews & Andrea Sorbi - 2018 - Annals of Pure and Applied Logic 169 (3):243-259.

View all 13 citations / Add more citations

References found in this work

Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.

View all 9 references / Add more references