- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Isomorphism relations on computable structures
Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán
Journal of Symbolic Logic 77 (1):122-132 (2012)
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 ωAuthor Profiles
Other Versions
No versions found
Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
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 (#277,905)
6 months
6 (#572,300)
2012-01-21
Downloads
78 (#277,905)
6 months
6 (#572,300)
Historical graph of downloads
Author Profiles
Citations of this work
Graphs realised by r.e. equivalence relations.Alexander Gavruskin, Sanjay Jain, Bakhadyr Khoussainov & Frank Stephan - 2014 - Annals of Pure and Applied Logic 165 (7-8):1263-1290.
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.
On the Structure of Computable Reducibility on Equivalence Relations of Natural Numbers.Uri Andrews, Daniel F. Belin & Luca San Mauro - 2023 - Journal of Symbolic Logic 88 (3):1038-1063.
Jumps of computably enumerable equivalence relations.Uri Andrews & Andrea Sorbi - 2018 - Annals of Pure and Applied Logic 169 (3):243-259.
References found in this work
Theory of recursive functions and effective computability.Hartley Rogers - 1987 - Cambridge: MIT Press.
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.
A borel reducibility theory for classes of countable structures.Harvey Friedman & Lee Stanley - 1989 - Journal of Symbolic Logic 54 (3):894-914.
Effective categoricity of equivalence structures.Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov - 2006 - Annals of Pure and Applied Logic 141 (1):61-78.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-8567d8d854-zpjm8 dc2