@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, inJournées algorithmiques, Astérisque, no. 38-39 (1976), pp. 3-21. http://www.numdam.org/item/AST_1976__38-39__3_0/

[1] A machine independent theory of the complexity of recursive functions. JACM, 14. | Article | MR 235912 | Zbl 0155.01503

: (1967)[2] On almost everywhere complex recursive functions. JACM, 21. | MR 457165 | Zbl 0315.68038

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

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

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

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

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

, : (1965)[8] Hierarchies of memory limited computations ; IEEE Conference on Switching, Circuit Theory and logical Design. | Zbl 0229.02033

, , : (1965)[9] An overview of the theory of computational complexity. JACM, 18. | Article | MR 288028 | Zbl 0226.68024

, : (1971)[10] 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

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

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

: (1973)[13] Inherent computational complexity of decision problems in logic and automata theory. In preparation.

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

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

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

: (1974)