×

A time-space tradeoff for sorting on non-oblivious machines. (English) Zbl 0462.68011


MSC:

68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science
68P10 Searching and sorting
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abelson, H., A note on time-space tradeoffs for computing continuous functions, Inform. Process. Lett., 8, 215-217 (1979) · Zbl 0412.68039
[2] Borodin, A.; Cook, S. A., A time-space tradeoff for sorting on a general sequential model of computation, (Proceedings, Twelfth Annual ACM Symposium on Theory of Computing. Proceedings, Twelfth Annual ACM Symposium on Theory of Computing, Los Angeles, CA (April 1980)), 294-301 · Zbl 0478.68061
[3] Cobham, A., The Recognition Problem for the Set of Perfect Squares, (Research Paper RC-1704 (April 1966), IBM Watson Research Center: IBM Watson Research Center Yorktown Heights, N.Y)
[4] Frederickson, G. N., Upper Bounds for Time-Space Trade-Offs in Sorting and Selection, (Technical Report CS-80-3 (January 1980), The Pennsylvania State University: The Pennsylvania State University University Park, PA) · Zbl 0642.68122
[5] Galil, Z.; Seiferas, J., Saving space in fast string-matching, (Proceedings, 18th Annual Symposium on Foundations of Computer Science. Proceedings, 18th Annual Symposium on Foundations of Computer Science, Providence, R.I. (Oct.-Nov. 1977)), 179-188
[6] Grigoryev, D. Yu., An application of separability and independence notions for proving lower bounds of circuit complexity, (Notes of Scientific Seminars No. 60 (1976), Steklovd Mathematical Institute, Leningrad Department), 38-48, (in Russian) · Zbl 0341.94020
[7] Knuth, D. E., (The Art of Computer Programming, Vol. 3, Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, Mass) · Zbl 0302.68010
[8] Lengauer, T.; Tarjan, R. E., Upper and lower bounds on time-space tradeoffs, (Proceedings, Eleventh Annual ACM Symposium on Theory of Computing. Proceedings, Eleventh Annual ACM Symposium on Theory of Computing, Atlanta, GA (April-May 1979)), 262-277
[9] Masek, W. J., A Fast Algorithm for the String Editing Problem and Decision Graph Complexity, (M. Sc. Thesis (May 1976), M.I.T)
[10] Munro, J. I.; Paterson, M. S., Selection and sorting with limited storage, (Proceedings, 19th Annual Symposium on Foundations of Computer Science. Proceedings, 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, MI (Oct. 1978)), 253-258 · Zbl 0441.68067
[11] Paul, W. J.; Tarjan, R. E., Time-space trade-offs in a pebble game, Acta Inform., 10, 111-115 (1978) · Zbl 0399.05030
[12] Pippenger, N., A time-space trade-off, J. Assoc. Comput. Mach., 25, 509-515 (1978) · Zbl 0379.68009
[13] Reingold, E. M., On the optimality of some set algorithms, J. Assoc. Comput. Mach., 19, 649-659 (1972) · Zbl 0246.68008
[14] Reischuk, R., Improved bounds on the problem of time-space trade-off in the pebble game, (Proceedings, 19th Annual Symposium on Foundations of Computer Science. Proceedings, 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, MI (Oct. 1978)), 84-91
[15] Savage, J. E.; Swamy, S., Space-time tradeoffs on the FFT algorithm, IEEE Trans. Inform. Theory, 24, 563-568 (1978) · Zbl 0379.65063
[16] Tompa, M., Time-space tradeoffs for computing functions, using connectivity properties of their cir-circuits, (Proceedings, Tenth Annual ACM Symposium on Theory of Computing. Proceedings, Tenth Annual ACM Symposium on Theory of Computing, San Diego, CA (May 1978)), 196-204 · Zbl 1282.68145
[17] Tompa, M., Time-Space Tradeoffs for Straight-Line and Branching Programs, (Ph. D. Thesis, Technical Report 122/78 (July 1978), University of Toronto)
[18] A. C., Yao, On the Time-Space Tradeoff for Sorting with Linear Queries, Stanford University.; A. C., Yao, On the Time-Space Tradeoff for Sorting with Linear Queries, Stanford University. · Zbl 0547.68062
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.