The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Hierarchies of memory limited computations
Abstract
This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A "translational" method which escapes some of the limitations of earlier approaches leads to a refinement of the established hierarchy. The previous complexity classes are shown to possess certain translational properties. An related hierarchy of complexity classes of monotonic functions is examined
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
On computable numbers, with an application to the entscheidungsproblem
Turing, A. M. (1937) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-42.1.230 · Cited by 8,283
On the computational complexity of algorithms
Hartmanis, J., & Stearns, R. E. (1965) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1965-0170805-7 · Cited by 1,006
Self-citationTwo-Tape Simulation of Multitape Turing Machines
Hennie, F. C., & Stearns, R. E. (1966) · Journal of the ACM · doi:10.1145/321356.321362 · Cited by 285
Self-citationClasses of predictably computable functions
Ritchie, R. W. (1963) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1963-0158822-2 · Cited by 248
Memory bounds for recognition of context-free and context-sensitive languages
Lewis, P., Stearns, R. E., & Hartmanis, J. (1965) · Annual Symposium on Switching Circuit Theory and Logical Design (SWCT) · doi:10.1109/focs.1965.14 · Cited by 243
Self-citationReal-Time Computation and Recursive Functions Not Real-Time Computable
Yamada, H. (1962) · IEEE Transactions on Electronic Computers · doi:10.1109/tec.1962.5219459 · Cited by 89
Cited by
Stockmeyer, L. J. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90061-x · Cited by 1,293
Recognition and parsing of context-free languages in time n3
Younger, D. H. (1967) · Information and Control · doi:10.1016/s0019-9958(67)80007-x · Cited by 935
The equivalence problem for regular expressions with squaring requires exponential space
Meyer, A. R., & Stockmeyer, L. J. (1972) · 13th Annual Symposium on Switching and Automata Theory (swat 1972) · doi:10.1109/swat.1972.29 · Cited by 596
Atchison, W. F., Conte, S. D., Hamblen, J. W., Hull, T. E., Keenan, T. A., Kehl, W. B., McCluskey, E. J., Navarro, S. O., Rheinboldt, W. C., Schweppe, E. J., et al. (1968) · Communications of the ACM · doi:10.1145/362929.362976 · Cited by 468
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Metadata
- Authors
- Stearns, R. E., Hartmanis, J., & Lewis, P. M.
- Venue
- 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965)
- Publisher
- IEEE
- Published
- 1965
- Pages
- 179-190
- OpenAlex
- W2533977282
- Cited by
- 352
- References
- 6
- FWCI
- 9.43
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Hierarchies of memory limited computations. https://app.cochat.ai/papers/10.1109/focs.1965.11
- The paper
- Stearns, R. E., Hartmanis, J., & Lewis, P. M. (1965). Hierarchies of memory limited computations. 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965). https://doi.org/10.1109/focs.1965.11
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.