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

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