A structure of punctual dimension two

DOI10.1090/proc/15020zbMath1442.03024OpenAlexW3004945185MaRDI QIDQ5111521

Keng Meng Ng, Alexander G. Melnikov

Publication date: 27 May 2020

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/proc/15020

zbMATH Keywords

computable structurecomputable dimensionprimitive recursivepunctual dimension

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Theory of numerations, effectively presented structures (03D45)

Related Items

Primitive recursive equivalence relations and their primitive recursive complexity ⋮ Punctually presented structures I: Closure theorems ⋮ Punctual dimension of algebraic structures in certain classes ⋮ Non-density in punctual computability ⋮ Computable embeddability for algebraic structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraic structures computable without delay
• Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
• Space complexity of abelian groups
• An on-line graph coloring algorithm with sublinear performance ratio
• Polynomial-time versus recursive models
• Polynomial-time Abelian groups
• On-line coloring \(k\)-colorable graphs
• Computable structures and the hyperarithmetical hierarchy
• Degree spectra and computable dimensions in algebraic structures
• Finite computable dimension and degrees of categoricity
• Structures computable in polynomial time. II
• Polynomial-time presentations of algebraic number fields
• The diversity of categoricity without delay
• Eliminating unbounded search in computable algebra
• Graphs are not universal for online computability
• The back-and-forth method and computability without delay
• Structures computable in polynomial time. I
• Turing's Legacy
• An introduction to computable model theory on groups and fields
• The additive group of the rationals does not have an automatic presentation
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• An Effective Version of Dilworth's Theorem
• On-Line Coloring and Recursive Graph Theory
• A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• CONSTRUCTIVE ALGEBRAS I
• COMPUTABLE FUNCTORS AND EFFECTIVE INTERPRETABILITY

This page was built for publication: A structure of punctual dimension two