Asymptotically tight bounds on time-space trade-offs in a pebble game

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	CHANDRA, A.K.Effictent compilation of linear recurslve programs. 14th Ann. IEEE Syrup. on Switching and Automata Theory, Ames, Iowa, 1973, pp. 16-25.
	2	COOK, S.A. An observation on time-storage trade-off. Z Comput. Syst. Sci. 9 (1974), 308-316.
	3	COOK, S.A., AND SETHI, R.Storage requirements for determinisUc polynomial finite recognizable languages. J. Comput Syst. Sa. 13 (1976), 25-37
	4	ERDos, P, GRAK~, R.L., AlqD Sz~mRF.DL E. On sparse graphs with dense long paths. Comp. Math. Appl. 1 (1975), 365-369.
	5	GABBER, O., AND GALIL, Z.Exphctt constructmn of linear stze concentrators and superconcentrators. 20th Ann. IEEE Symp on Foundations of Computer Scmnce, San Juan, Puerto Rico, 1979, pp. 364-370.
	6	GILBERT, J.R., LENGAtam, T., At~O T~AN, R.E.The pebbling problem is complete in polynomial space SIAM J Comput. 9 (1980), 513-524
	7	John R. Gilbert , Robert E Tarjan, Variations of a pebble game on graphs, Stanford University, Stanford, CA, 1978
	8	HnwIrr, C.E, ^~D P^aXRSON, M.S.Comparative schematology Project MAC Conf. on Concurrent Systems and Parallel Computation, Woods Hole, Mass, 1970, pp. 119-127.
	9	John Hopcroft , Wolfgang Paul , Leslie Valiant, On Time Versus Space, Journal of the ACM (JACM), v.24 n.2, p.332-337, April 1977 [doi>10.1145/322003.322015]
	10	Joseph Ja'Ja', Time-space tradeoffs for some algebraic problems, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.339-350, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804683]
	11	Thomas Lengauer , Robert Endre Tarjan, Upper and lower bounds on time-space tradeoffs, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.262-277, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804420]
	12	Andrzej Lingas, A PSPACE Complete Problem Related to a Pebble Game, Proceedings of the Fifth Colloquium on Automata, Languages and Programming, p.300-321, July 17-21, 1978
	13	Lool, M.C. A note on the pebble game Inf. Proc Lett. 11 (1980), 24--26
	14	MARGULIS, G.A.Expliot construchons of concentrators. Problem), Peredachi Informatsii 9 (1973), 71-80 (English trans, in: Problems of Information Transmtss:on, Plenum, New York, 1975).
	15	Friedhelm Meyer auf der Heide, A Comparison Between Two Variations of a Pebble Game on Graphs, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.411-421, July 16-20, 1979
	16	PALrL, W.J. On time hxerarehaes. 8th Ann ACM Symp. on Theory of Computing, Hershey, P~,., 1976, pp. 218-222
	17	PAUL, W.J., AND REISCHUK, R.On alternation I1. A graph theoreuc approach to determinism versus nondetermmlsm Acta lnf 14 (1980), 391--403.
	18	PAUL, W.J., AND TARJAN, R.E. Ttme-space trade-offs in a pebble game Acta. Inf 10 (1978), 111-115.
	19	PAUL, W J., TARIAN, R.E., AND CELOr~I, J.R Space bounds for a game on graphs. Math. Syst. Theory I0 (1977), 239-251.
	20	PINSKE~, M.S.On the complexity of a concentrator. Proc. 7th Int. Teletraffic Congress, Stockholm, 1973, pp. 318/1-318/4 (available from Secretariat, Televerket S-12386, Farsta, Sweden)
	21	PlPPENGER, N.Superconcentrators. SlAM ~ ComImt. 6 (1977), 298-304.
	22	Nicholas Pippenger, A Time-Space Trade-Off, Journal of the ACM (JACM), v.25 n.3, p.509-515, July 1978 [doi>10.1145/322077.322091]
	23	Nicholas Pippenger, Comparative schematology and pebbling with auxiliary pushdowns (Preliminary Version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.351-356, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804684]
	24	Rudiger Reischuk, Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game, Journal of the ACM (JACM), v.27 n.4, p.839-849, Oct. 1980 [doi>10.1145/322217.322233]
	25	SCmCrrGER, G.A family of graphs with expenswe depth-reduction. Fakultat fur Mathemattk, Universttat Blelefeld, Bielefeld, W. Germany, 1980
	26	SAVAGE, J.E., AND SWAMY, S.Space-time trade-offs on the FFT-algonthm. Tech. Rep. CS-31, Brown Univ., Providence, R.I., 1977.
	27	John E. Savage , Sowmitri Swamy, Space-Time Tradeoffs for Oblivious Interger Multiplications, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.498-504, July 16-20, 1979
	28	Sowmitri Swamy , John E. Savage, Space-time tradeoffs for linear recursion, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.135-142, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567765]
	29	SETm, R.Complete register allocation problems. SIAM~ Comput. 4 (1975), 226-248.
	30	Martin Tompa, Time-space tradeoffs for computing functions, using connectivity properties of their circuits, Proceedings of the tenth annual ACM symposium on Theory of computing, p.196-204, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804348]
	31	Martin Tompa, Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.333-338, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804682]
	32	VALIAr~r, L.G Graph-theoretic propemes m computational complexity. ~ Comput. Syst. Sc~ 13 (1976), 278--285.
	33	VALIANt, L.G.Graph-theoretic arguments m low level complexity. Symp. on Mathematwal Foundations of Computer Science, Lecture Notes in Computer Science 53, Sprmger-Verlag, New York, 1977, pp. 162-176
	34	Peter van Emde Boas , Jan van Leeuwen, Move Rules and Trade-Offs in the Pebble Game, Proceedings of the 4th GI-Conference on Theoretical Computer Science, p.101-112, March 26-28, 1979