An observation on time-storage trade off. (English) Zbl 0306.68026


68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Cook, S.A., The complexity of theorem-proving procedures, (), 151-158 · Zbl 0363.68125
[2] Karp, R.M., Reducibilities among combinatorial problems, (), 85-103
[3] {\scP. M. Lewis II, R. E. Stearns, and J. Hartmanis}, Memory Bounds for the Recognition of Context-Free and Context-Sensitive Languages, “IEEE Conference Record on 1965 Symposium on Switching Circuit Theory and Logical Design,” Institute of Electrical and Electronics Engineers, New York · Zbl 0272.68054
[4] Hopcroft, J.E.; Ullman, J.D., ()
[5] Cook, S.A., Path systems and language recognition, (), 70-72
[6] Cook, S.A., Characterizations of pushdown machines in terms of time-bounded computers, J. assoc. comput. Mach., 18, 4-18, (1971) · Zbl 0222.02035
[7] Paterson, M.S.; Hewitt, C.E., Comparative schematology, (), 119-128 · Zbl 0401.68002
[8] Walker, S.A.; Strong, H.R., Characterizations of flow-chartable recursions, short version, (), 18-34 · Zbl 0354.68029
[9] Savitch, W.J., Maze recognizing automata and nondeterministic tape complexity, J. comput. system sci., 7, 389-403, (1973) · Zbl 0273.02022
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.