Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-25T10:31:27.475Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  12 March 2014

Serge Grigorieff
Serge Grigorieff*
Affiliation:
Laboratoire D'Informatique Théorique et Programmation, Université Paris-VII, 75251 Paris, France
Get access Rights & Permissions [Opens in a new window]

Extract

This paper is a contribution to the following natural problem in complexity theory:

(*) Is there a complexity theory for isomorphism types of recursive countable relational structures? I.e. given a recursive relational structure ℛ over the set N of nonnegative integers, is there a nontrivial lower bound for the time-space complexity of recursive structures isomorphic (resp. recursively isomorphic) to ℛ?

For unary recursive relations R, the answer is trivially negative: either R is finite or coinfinite or 〈N, R〉 is recursively isomorphic to 〈N, {x ϵ N: x is even}〉.

The general problem for relations with arity 2 (or greater) is open.

Related to this problem, a classical result (going back to S. C. Kleene [4], 1955) states that every recursive ordinal is in fact primitive recursive.

In [3] Patrick Dehornoy, using methods relevant to computer science, improves this result, showing that every recursive ordinal can be represented by a recursive total ordering over N which has linear deterministic time complexity relative to the binary representation of integers. As he notices, his proof applies to every recursive total order type α such that the isomorphism type of α is not changed if points are replaced by arbitrary finite nonempty subsets of consecutive points.

In this paper we extend Dehornoy's result to all recursive total orderings over N and get minimal complexity for both time and space simultaneously.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 55 , Issue 1 , March 1990 , pp. 260 - 276
Copyright
Copyright © Association for Symbolic Logic 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Cenzer, Douglas and Remmel, Jeffrey, Polynomial-time complexity of models (to appear).Google Scholar
[2]Cobham, Alan, On the base-dependence of sets of numbers recognizable by finite automata, Mathematical Systems Theory, vol. 3 (1969), 186–192.CrossRefGoogle Scholar
[3]Dehornoy, Patrick, Turing complexity of the ordinals, Information Processing Letters, vol. 23 (1986), pp. 167–170.CrossRefGoogle Scholar
[4]Kleene, Stephen C., On the forms of the predicates in the theory of constructive ordinals. II, American Journal of Mathematics, vol. 77 (1955), pp. 405–428.CrossRefGoogle Scholar
[5]Moses, Michael, Recursive linear orders with recursive successivities, Annals of Pure and Applied Logic, vol. 27 (1984), pp. 253–264.CrossRefGoogle Scholar
[6]Remmel, Jeffrey, Recursive isomorphism types of recursive Boolean algebras, this Journal, vol. 46 (1981), pp. 572–594.Google Scholar
[7]Remmel, Jeffrey, Recursively categorical linear orderings, Proceedings of the American Mathematical Society, vol. 83 (1981), pp. 387–391.CrossRefGoogle Scholar
[8]Rosenstein, Joseph G., Linear orderings, Academic Press, New York, 1982.Google Scholar
[9]Stearns, R. E., Hartmanis, J. and Lewis, P. M., Hierarchies of memory limited computations, Proceedings of the IEEE conference on switching, circuit theory and logical design, IEEE, 1965, pp. 179–190.Google Scholar
[10]Watnick, Richard, A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings, this Journal, vol. 49 (1984), pp. 563–569Google Scholar
[11]Wagner, Klaus and Wechsung, Gerd, Computational complexity, Reidel, Dordrecht, 1986.Google Scholar