Space-time tradeoffs in computations
Journées algorithmiques, Astérisque, no. 38-39 (1976), p. 253-264
@incollection{AST_1976__38-39__253_0,
     author = {Valiant, L. G.},
     title = {Space-time tradeoffs in computations},
     booktitle = {Journ\'ees algorithmiques},
     author = {Collectif},
     series = {Ast\'erisque},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {38-39},
     year = {1976},
     pages = {253-264},
     zbl = {0359.68052},
     mrnumber = {451863},
     language = {en},
     url = {http://www.numdam.org/item/AST_1976__38-39__253_0}
}
Valiant, L. G. Space-time tradeoffs in computations, in Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 253-264. http://www.numdam.org/item/AST_1976__38-39__253_0/

[1] Aho, A. V., J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. | Zbl 0326.68005

[2] Book, R. V.Comparing complexity classes. JCSS 9 (1974) 213-229. | MR 366099 | Zbl 0331.02020

[3] Borodin, A.Some remarks on time-space and size-depth Manuscript (1975).

[4] Cook, S. A.The Complexity of theorem-proving procedures. Proc. 3rd ACM Symp. on Theory of Computing (1971) 151-158. | Zbl 0253.68020

[5] Cook, S. A. An observation on time-storage tradeoff. Proc. 5th ACM Symp. on Theory of Computing (1973) 29-33. | MR 411238 | Zbl 0305.68066

[6] Cook, S. A. and R. Sethi. Storage requirements for deterministic polynomial time recognizable languages. Proc. 6th ACM Symp. on Theory of Computing (1974) 33-39. | MR 421161 | Zbl 0412.68078

[7] Even, S. and R. E. Tarjan. A combinatorial problem that is complete in polynomial space. Proc. 7th ACM Symp. on Theory of Computing (1975) 66-71. | MR 451852

[8] Hennie, F. C. and R. E. Stearns. Two tape simulations of multi-tape machines. JACM 13 (1966) 533-546. | Article | MR 210521 | Zbl 0148.24801

[9] Hopcroft, J. E. and J. D. Ullman. Relations between tape and time complexities. JACM 15 (1968) 414-427. | Article | MR 235918 | Zbl 0169.31103

[10] Hopcroft, J. E., W. J. Paul and L. G. Valiant. On time versus space and related problems. Proc. 16th IEEE Symp. on Foundations of Computer Science (1975) 57-64. | MR 428789

[11] Hopcroft, J. E. and J. D. Ullman. Formal Languages and their Relation to Automata. Addison-Wesley, (1969). | MR 237243 | Zbl 0196.01701

[12] Jones, N. D. and W. T. Laaser. Complete problems for deterministic polynomial time. Proc. 6th ACM Symp. on Theory of Computing (1974) 40-46. | MR 438800 | Zbl 0376.68040

[13] Karp, R. M.Reducibility among combinatorial problems. In Miller, R.E. and J.W. Thatcher (eds.). Complexity of Computer Computations, Plenum Press (1972). | Article | MR 378476 | Zbl 0366.68041

[14] Landweber, P. S.Three theorems on phrase structure grammars of type 1. Inf. and Control 6 (1963) 131-137. | Article | MR 166011 | Zbl 0116.11702

[15] Meyer, A. R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. Proc. 13th IEEE Symp. on Switching and Automata Theory (1972) 125-129.

[16] Paterson, M. S. and C. E. Hewitt. Comparative schematology. Proc. of Project MAC Conf. on Concurrent Syst. and Parallel Compt. (1970) 119-127.

[17] Paterson, M. S. and L. G. Valiant. Circuit size is nonlinear in depth. TCS (to appear). | Article | MR 414247 | Zbl 0345.94026

[18] Paul, W. J., R. E. Tarjan and J. R. Celoni. Space bounds for a game on graphs. Proc. 8th ACM Symp. on Theory of Computing (1976). | MR 445906 | Zbl 0365.05027

[19] Stearns, R. E., J. Hartmanis, and P. M. Lewis. Hierarchies of memory limited computations. Proc. of 6th IEEE Symp. of Switching and Automata Theory (1965) 191-202.

[20] Stockmeyer, L. and A. R. Meyer.Word problems requiring exponential time. Proc. 5th ACM Symp. on Theory of Computing (1973) 1-9. | MR 418518 | Zbl 0359.68050

[21] Valiant, L. G.Universal Circuits. Proc. 8th ACM Symp. on Theory of Computing (1976). | Zbl 0365.94044