Difficult logical theories and their computer approximations
Journées algorithmiques, Astérisque no. 38-39  (1976), p. 3-21
@incollection{AST_1976__38-39__3_0,
author = {Ausiello, Giorgio},
title = {Difficult logical theories and their computer approximations},
booktitle = {Journ\'ees algorithmiques},
author = {Collectif},
series = {Ast\'erisque},
publisher = {Soci\'et\'e math\'ematique de France},
number = {38-39},
year = {1976},
pages = {3-21},
mrnumber = {476470},
zbl = {0365.02022},
language = {en},
url = {http://www.numdam.org/item/AST_1976__38-39__3_0}
}

Ausiello, Giorgio. Difficult logical theories and their computer approximations, in Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 3-21. http://www.numdam.org/item/AST_1976__38-39__3_0/

[1] Blum M. : (1967) A machine independent theory of the complexity of recursive functions. JACM, 14. | Article | MR 235912 | Zbl 0155.01503

[2] Blum M., Gill J. : (1974) On almost everywhere complex recursive functions. JACM, 21. | MR 457165 | Zbl 0315.68038

[3] Ferrante J. : (1974) Some upper and lower bounds on decision procedures in logic. Doctoral Thesis, Dept. of Mathematics, M.I.T., Cambridge, Mass.

[4] Fisher M. J., Rabin M. O. : (1974) Super exponential complexity of Presburger arithmetic. Proj. MAC Tech. Memo 43M.I.T., Cambridge, Mass. | MR 366646 | Zbl 0319.68024

[5] Flajolet P., Steyaert J. M. : (1974) On sets having only hard subsets. Second colloquium on Automata, Languages and Programming, Saarbrücken, Germany. | MR 424541

[6] Gold M. : (1965) Limiting recursion. J.S.L., 30. | MR 239972 | Zbl 0203.01201

[7] Hartmanis J., Stearns R. E. : (1965) On the computational complexity of algorithms. Trans. AMS, 117. | Article | MR 170805 | Zbl 0131.15404

[8] Hartmanis J., Lewis P. M., Stearns R. E. : (1965) Hierarchies of memory limited computations ; IEEE Conference on Switching, Circuit Theory and logical Design. | Zbl 0229.02033

[9] Hartmanis J., Hopcroft J. E. : (1971) An overview of the theory of computational complexity. JACM, 18. | Article | MR 288028 | Zbl 0226.68024

[10] Hartmanis J. : (1975) On effective speed-up and long proofs of trivial theorems in formal theories. Dept. of Computer Science, Cornell University, Ithaca, N.Y. | Zbl 0399.03041

[11] Meyer A. R. : (1972). The inherent difficulty of logical theories. School on Algorithms and Complexity, Oberwolfach, Germany.

[12] Meyer A. R. : (1973) Weak monadic second order theory of successor is not elementary recursive. Proj. MAC, Tech. Memo 38, M.I.T., Cambridge, Mass. | Zbl 0326.02036

[13] Meyer A. R., Stockmeyer L. J. : (1975) Inherent computational complexity of decision problems in logic and automata theory. In preparation.

[14] Rabin M. O. : (1974) Theoretical impediments to artificial intelligence. IFIP Congress, Stockholm, Sweden. | MR 421186 | Zbl 0296.68054

[15] Rackoff C. : (1974) Complexity of some logical theories. Doctoral Thesis, Dept. of El. Eng., M.I.T., Cambridge, Mass.

[16] Stockmeyer L. J. : (1974) The complexity of decision problems in automata theory and logic. Doctoral Thesis, Dept. of El. Eng., M.I.T.Cambridge, Mass.