Space-time tradeoffs in computations

Valiant, L. G.

Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 253-264.

MR Zbl

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

TY  - CHAP
AU  - Valiant, L. G.
TI  - Space-time tradeoffs in computations
BT  - Journées algorithmiques
AU  - Collectif
T3  - Astérisque
PY  - 1976
SP  - 253
EP  - 264
IS  - 38-39
PB  - Société mathématique de France
UR  - http://www.numdam.org/item/AST_1976__38-39__253_0/
LA  - en
ID  - AST_1976__38-39__253_0
ER  -

%0 Book Section
%A Valiant, L. G.
%T Space-time tradeoffs in computations
%B Journées algorithmiques
%A Collectif
%S Astérisque
%D 1976
%P 253-264
%N 38-39
%I Société mathématique de France
%U http://www.numdam.org/item/AST_1976__38-39__253_0/
%G en
%F AST_1976__38-39__253_0

Valiant, L. G. Space-time tradeoffs in computations, dans Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 253-264. http://www.numdam.org/item/AST_1976__38-39__253_0/

Bibliographie
Cité par

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

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

[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

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

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

[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

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

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

[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

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

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

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

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

[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). | DOI | MR | Zbl

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

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

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