- 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
On the complexity of categoricity in computable structures
Mathematical Logic Quarterly 49 (6):603 (2003)
Abstract
We investigate the computational complexity the class of Γ-categorical computable structures. We show that hyperarithmetic categoricity is Π11-complete, while computable categoricity is Π04-hardMy notes
Similar books and articles
Degrees of categoricity of computable structures.Ekaterina B. Fokina, Iskander Kalimullin & Russell Miller - 2010 - Archive for Mathematical Logic 49 (1):51-67.
Categoricity of computable infinitary theories.W. Calvert, S. S. Goncharov, J. F. Knight & Jessica Millar - 2009 - Archive for Mathematical Logic 48 (1):25-38.
Equivalence structures and isomorphisms in the difference hierarchy.Douglas Cenzer, Geoffrey LaForte & Jeffrey Remmel - 2009 - Journal of Symbolic Logic 74 (2):535-556.
Intrinsic bounds on complexity and definability at limit levels.John Chisholm, Ekaterina B. Fokina, Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Sara Quinn - 2009 - Journal of Symbolic Logic 74 (3):1047-1060.
Applications of Kolmogorov Complexity to Computable Model Theory.B. Khoussainov, P. Semukhin & F. Stephan - 2007 - Journal of Symbolic Logic 72 (3):1041 - 1054.
Computable categoricity of trees of finite height.Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Journal of Symbolic Logic 70 (1):151-215.
Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures.Walker M. White & Denis R. Hirschfeldt - 2002 - Notre Dame Journal of Formal Logic 43 (1):51-64.
Finite computable dimension does not relativize.Charles F. D. McCoy - 2002 - Archive for Mathematical Logic 41 (4):309-320.
Prime models of finite computable dimension.Pavel Semukhin - 2009 - Journal of Symbolic Logic 74 (1):336-348.
On Computability Theoretic Properties of Structures and Their Cartesian Products.Bakhadyr Khoussainov - 2000 - Mathematical Logic Quarterly 46 (4):467-476.
Categoricity and indefinite extensibility.James Walmsley - 2002 - Proceedings of the Aristotelian Society 102 (3):217–235.
Analytics
Added to PP
2013-12-01
Downloads
11 (#1,065,379)
6 months
4 (#657,928)
2013-12-01
Downloads
11 (#1,065,379)
6 months
4 (#657,928)
Historical graph of downloads
Citations of this work
Scott sentences for certain groups.Julia F. Knight & Vikram Saraph - 2018 - Archive for Mathematical Logic 57 (3-4):453-472.
Computably Isometric Spaces.Alexander G. Melnikov - 2013 - Journal of Symbolic Logic 78 (4):1055-1085.
Computable categoricity of trees of finite height.Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Journal of Symbolic Logic 70 (1):151-215.
Index Sets for Classes of High Rank Structures.W. Calvert, E. Fokina, S. S. Goncharov, J. F. Knight, O. Kudinov, A. S. Morozov & V. Puzarenko - 2007 - Journal of Symbolic Logic 72 (4):1418 - 1432.
2010 North American Annual Meeting of the Association for Symbolic Logic.Reed Solomon - 2011 - Bulletin of Symbolic Logic 17 (1):127-154.
References found in this work
A borel reducibility theory for classes of countable structures.Harvey Friedman & Lee Stanley - 1989 - Journal of Symbolic Logic 54 (3):894-914.
Computably categorical structures and expansions by constants.Peter Cholak, Sergey Goncharov, Bakhadyr Khoussainov & Richard A. Shore - 1999 - Journal of Symbolic Logic 64 (1):13-37.
Computable isomorphisms, degree spectra of relations, and Scott families.Bakhadyr Khoussainov & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 93 (1-3):153-193.
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-6d9b7f7c4c-67rzb uwo