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

DOI10.2307/2274966zbMath0708.03015MaRDI 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

time; space; recursive ordinal; minimal complexity; recursive total orderings over N

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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

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