Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))

DOI10.2307/2274966zbMath0708.03015OpenAlexW2165339507MaRDI QIDQ3489983

Serge Grigorieff

Publication date: 1990

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2274966

zbMATH Keywords

timespacerecursive ordinalminimal complexityrecursive total orderings over N

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (28)

Definable Subsets of Polynomial-Time Algebraic Structures ⋮ Structures computable in polynomial time. I ⋮ Complexity and categoricity ⋮ Punctual copies of algebraic structures ⋮ Graphs are not universal for online computability ⋮ Primitive recursive reverse mathematics ⋮ Punctual 1-linear orders ⋮ Feasibly categorical models ⋮ A structure of punctual dimension two ⋮ Primitive recursive ordered fields and some applications ⋮ Preface ⋮ Polynomial-time versus recursive models ⋮ Polynomial-time Abelian groups ⋮ Algebraic structures computable without delay ⋮ Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization ⋮ Eliminating unbounded search in computable algebra ⋮ The back-and-forth method and computability without delay ⋮ Punctual dimension of algebraic structures in certain classes ⋮ AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES ⋮ Non-density in punctual computability ⋮ Space complexity of abelian groups ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ Complexity, decidability and completeness ⋮ Feasible graphs with standard universe ⋮ Unnamed Item ⋮ PUNCTUAL CATEGORICITY AND UNIVERSALITY ⋮ Computable embeddability for algebraic structures ⋮ Searching for applicable versions of computable structures

Cites Work

• Unnamed Item
• Unnamed Item
• Turing complexity of the ordinals
• Recursive linear orders with recursive successivities
• On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)
• A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
• On the base-dependence of sets of numbers recognizable by finite automata

This page was built for publication: Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))