The complexity of logical theories. (English) Zbl 0475.03017


03D15 Complexity of computation (including implicit computational complexity)
03D10 Turing machines and related notions
Full Text: DOI


[1] Berman, L., Precise bounds for Presburger arithmetic and the reals with addition: preliminary report, Proc. 18th Annual IEEE Foundations of Computer Science Conference, 95-99, (1977)
[2] L. Berman, Complexity of QBF, to appear.
[3] Bruss, A.; Meyer, A., On time-space classes and their relation to the theory of real addition, Theoret. Comput. Sci., 11, 59-69, (1980), this journal. · Zbl 0467.03038
[4] A. Chandra, D. Kozen and L. Stockmeyer, Alternation, J. ACM, to appear.
[5] Ferrante, J.; Rackoff, C., A decision procedure for the first order theory of real addition with order, SIAM J. Comput., 4, 1, 69-76, (1975) · Zbl 0294.02022
[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] Oppen, D. C., A 2^{2}^{2}^{pn} upper bound on the complexity of Presburger arithmetic, J. Comput. System Sci., 16, 3, 323-332, (1978) · Zbl 0381.03021
[8] Stockmeyer, L., The complexity of decision problems in automata theory and logic, (Project MAC, TR-133, (1974), MIT Cambridge, MA)
[9] Stockmeyer, L.; Meyer, A., Word problems requiring exponential time: preliminary report, Proc. 5th SIGACT, 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.