Using computability to measure complexity of algebraic structures and classes of structures

DOI10.1134/S1995080214040192zbMath1325.03036MaRDI QIDQ2263109

Julia F. Knight

Publication date: 17 March 2015

Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

classes of structuresmeasure complexitycomputable algebraic structures

Mathematics Subject Classification ID

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

Related Items

Categoricity spectra for polymodal algebras ⋮ Turing computable embeddings, computable infinitary equivalence, and linear orders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computable structures and the hyperarithmetical hierarchy
• Degree spectra and computable dimensions in algebraic structures
• A computability theoretic equivalent to Vaught's conjecture
• The theory of models. Proceedings of the 1963 international symposium at Berkeley
• The syntax and semantics of infinitary languages
• CLASSES OF STRUCTURES WITH NO INTERMEDIATE ISOMORPHISM PROBLEMS
• Describing free groups
• Describing free groups, Part II: Π⁰₄ hardness and no Σ₂⁰ basis
• The Slaman-Wehner theorem in higher recursion theory
• A Borel reductibility theory for classes of countable structures
• Recursive well-orderings
• THE WORD PROBLEM
• Degree spectra and immunity properties
• Spectra of Algebraic Fields and Subfields
• Degrees coded in jumps of orderings
• Reducibility and Completeness for Sets of Integers
• Relative to any nonrecursive set
• Enumerations, countable structures and Turing degrees
• Degrees of Structures
• The decomposability problem for torsion-free abelian groups is analytic-complete
• The effective Borel hierarchy
• Isomorphism relations on computable structures
• Isomorphism of Computable Structures and Vaught's Conjecture
• Turing computable embeddings
• Comparing Classes of Finite Structures
• An interpolation theorem for denumerably long formulas
• DIOPHANTINE REPRESENTATION OF ENUMERABLE PREDICATES
• On definable sets of positive integers
• Recursive Predicates and Quantifiers