zbMATH — the first resource for mathematics

On time-space classes and their relation to the theory of real addition. (English) Zbl 0467.03038

03D15 Complexity of computation (including implicit computational complexity)
03B25 Decidability of theories and sets of sentences
Full Text: DOI
[1] Berman, L., Precise bounds for Presburger arithmetic and the reals with addition: preliminary report, Proc. 18th Annual Symposium on Foundations of Computer Science, 95-99, (1977)
[2] Berman, L., The complexity of logical theories, Theoret. Comput. Sci., 11, 71-77, (1980), this journal. · Zbl 0475.03017
[3] Chandra, A. K.; Stockmeyer, L. J., Alternation, Proc. 17th Annual Symposium on Foundations of Computer Science, 98-108, (1976)
[4] Ferrante, J.; Rackoff, C. W., A decision procedure for the first order theory of real addition with order, SIAM J. Comput., 4, 1, 69-76, (1975) · Zbl 0294.02022
[5] Ferrante, J.; Rackoff, C. W., The computational complexity of logical theories, (Lecture Notes in Mathematics, (1979), Springer Berlin) · Zbl 0404.03028
[6] Fischer, M. J.; Rabin, M. O., Super-exponential complexity of Presburger arithmetic, (SIAM-AMS Proc., VII, (1974), AMS Providence, RI) · Zbl 0319.68024
[7] Fleischmann, K.; Mahr, B.; Siefkes, D., Bounded concatenation theory as a uniform method for proving lower complexity bounds, (Gandy, R. O.; Hyland, J. M.E., Logic Colloquium 76, (1977), North-Holland Amsterdam), 471-490
[8] Fleischmann, K.; Mahr, B.; Siefkes, D., Complexity of decision problems, (Bericht Nr. 76-09, (1976), Technische Universität Berlin)
[9] Glinert, E. P., On restricting Turing computability, Math. Systems Theory, 5, 4, 331-343, (1971) · Zbl 0226.02038
[10] Hopcroft, J. E.; Ullman, J. D.; Hopcroft, J. E.; Ullman, J. D., (Formal Languages and their Relation to Automata, (1969), Addison-Wesley Reading, MA), 149-155 · Zbl 0196.01701
[11] Knuth, D. E., Big omicron and big omega and big theta, Sigact News, 8, 2, 19, (1976)
[12] Kozen, D., On parallelism in Turing machines, Proc. 17th Annual Symposium on Foundations of Computer Science, 89-97, (1976)
[13] Lind, J. C., Computing in logarithmic space, MIT Project MAC TM 52, (1974)
[14] Rackoff, C. W., The computational complexity of some logical theories, MIT Project MAC TR 144, 118-127, (1975)
[15] Seiferas, J. I., Techniques for separating space complexity classes, J. Comput. System Sci., 14, 1, 73-99, (1977) · Zbl 0352.68062
[16] Seiferas, J. I.; Fischer, M. J.; Meyer, A. R., Separating nondeterministic time complexity classes, J. ACM, 25, 1, 146-167, (1978) · Zbl 0366.68038
[17] Stockmeyer, L. J., The complexity of decision problems in automata theory and logic, MIT Project MAC TR 133, (1974)
[18] Stockmeyer, L. J., The polynomial time hierarchy, Theoret. Computer Sci., 3, 1-22, (1977) · Zbl 0353.02024
[19] Stockmeyer, L. J.; Meyer, A. R., Word problems requiring exponential time: preliminary report, Proc. 5th Annual ACM Symposium on Theory of Computing, 1-9, (1973) · Zbl 0359.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.