Difficult logical theories and their computer approximations
Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 3-21 
@incollection{AST_1976__38-39__3_0,
     author = {Ausiello, Giorgio},
     title = {Difficult logical theories and their computer approximations},
     booktitle = {Journ\'ees algorithmiques},
     series = {Ast\'erisque},
     pages = {3--21},
     year = {1976},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {38-39},
     zbl = {0365.02022},
     mrnumber = {476470},
     language = {en},
     url = {https://www.numdam.org/item/AST_1976__38-39__3_0/}
}
TY  - CHAP
AU  - Ausiello, Giorgio
TI  - Difficult logical theories and their computer approximations
BT  - Journées algorithmiques
AU  - Collectif
T3  - Astérisque
PY  - 1976
SP  - 3
EP  - 21
IS  - 38-39
PB  - Société mathématique de France
UR  - https://www.numdam.org/item/AST_1976__38-39__3_0/
LA  - en
ID  - AST_1976__38-39__3_0
ER  - 
%0 Book Section
%A Ausiello, Giorgio
%T Difficult logical theories and their computer approximations
%B Journées algorithmiques
%A Collectif
%S Astérisque
%D 1976
%P 3-21
%N 38-39
%I Société mathématique de France
%U https://www.numdam.org/item/AST_1976__38-39__3_0/
%G en
%F AST_1976__38-39__3_0
Ausiello, Giorgio. Difficult logical theories and their computer approximations, dans Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 3-21. https://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. | MR | Zbl | DOI

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

[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 | Zbl

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

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

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

[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

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

[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

[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

[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 | Zbl

[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.