×

White pebbles help. (English) Zbl 0657.68049

Author’s summary: “It is proved that for infinitely many n there is a directed acyclic graph with vertex indegrees bounded by 2 that has a strategy of the black-white pebble game using n pebbles and for which any strategy of the black pebble game requires \(\Omega\) (n log n/log log n) pebbles. This shows that there is a family of straight-line programs for which nondeterminism reduces the space required to evaluate the programs by more than any constant factor.”
Reviewer: R.Klette

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D15 Complexity of computation (including implicit computational complexity)
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cook, S. A., An observation on time-storage trade-off, J. Comput. System Sci., 9, 308-316 (1974) · Zbl 0306.68026
[2] Cook, S. A.; Sethi, R., Storage requirements for deterministic polynomial finite recognizable languages, J. Comput. System Sci., 13, 25-37 (1976) · Zbl 0337.68031
[3] Friedman, H., Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory, (Gandy, R. O.; Yates, C. M.E., Logic Colloquium ’69 (1970), North-Holland: North-Holland Amsterdam), 361-389
[4] Hewitt, C. E.; Paterson, M. S., Comparative schematology, (Proceedings, Project MAC Conference on Concurrent Systems and Parallel Computation. Proceedings, Project MAC Conference on Concurrent Systems and Parallel Computation, Woods Hole, Mass. (1970)), 119-127 · Zbl 0401.68002
[5] Klawe, M. M., A tight bound for black and white pebbles on the pyramid, J. Assoc. Comput. Mach., 32, No. 1, 218-228 (1985) · Zbl 0632.68042
[6] Lengauer, T.; Tarjan, R., The space complexity of pebble games on trees, Inform. Process. Lett., 10, 184-188 (1980) · Zbl 0449.68028
[7] Lengauer, T.; Tarjan, R., Asymptotically tight bounds on time-space trade-offs in a pebble game, J. Assoc. Comput. Mach., 29, No. 4, 1087-1130 (1982) · Zbl 0495.68037
[8] Loui, M. C., The Space Complexity of Two Pebble Games on Trees, (TM-133 (1979), Laboratory for Computer Science, Massachusetts Institute of Technology)
[9] Meyer auf der Heide, F., A comparison of two variations of a pebble game on graphs, Theoret. Comput. Sci., 13, 315-322 (1981) · Zbl 0454.05031
[10] Pippenger, N., Pebbling, IBM Research Report RC 8258 (1980)
[11] Pippenger, N., Advances in pebbling, (Nielson, M.; Schmidt, E. M., Proceedings, Ninth Int. Colloq. on Automata, Languages, and Programming. Proceedings, Ninth Int. Colloq. on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 140 (1982), Springer-Verlag: Springer-Verlag New York), 407-417
[12] Savitch, W. J., Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 4, 177-192 (1970) · Zbl 0188.33502
[13] Wilber, R. E., A Comparison of the Black and Black-White Pebble Games, (Ph.D. thesis (1985), Carnegie-Mellon University)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.