×

zbMATH — the first resource for mathematics

Tape-reversal bounded Turing machine computations. (English) Zbl 0259.68020

MSC:
68Q25 Analysis of algorithms and problem complexity
03D10 Turing machines and related notions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Blum, M., J. ACM, 14, 322-336, (1967)
[2] Hartmanis, J.; Stearns, R.E., Trans. am. math. soc., 117, 285-306, (1965)
[3] Hartmanis, J.; Lewis, P.M.; Strearns, R.E., Classification of computations by time and memory requirements, (), 31-35
[4] Hennie, F.C., Inform. control, 8, 553-578, (1965)
[5] \scJ. Hartmanis. Computational Complexity of One-Tape Turing Machine Computations. J. ACM (to be published). · Zbl 0223.02037
[6] Rabin, M.O., Israel J. math., 1, 203-211, (1963)
[7] Ritchie, R.W., Trans. am. math. soc., 106, 139-173, (1963)
[8] Kasami, T., An efficient recognition and syntax-analysis algorithm for context-free languages, Report of university of hawaii, contract no. AF 19(628)-4379, No. 2, (1965)
[9] Younger, D.H., Inform. control, 10, 189-208, (1967)
[10] Lewis, P.M.; Stearns, R.E.; Hartmanis, J., Memory bounds for recognition of context-free and context-sensitive languages, (), 191-202 · Zbl 0272.68054
[11] Hopcroft, J.E.; Ullman, J.D., J. computer syst. sci., 1, 166-186, (1967)
[12] Hartmanis, J., On the complexity of undecidable problems in automata theory, () · Zbl 0182.02403
[13] Minsky, M.; Papert, S., J. ACM, 31, 281-286, (1966)
[14] \scJ. Hartmanis and H. Shank. On the Recognition of Primes by Automata. J. ACM (to be published). · Zbl 0164.05201
[15] \scM. Blum, private communication.
[16] Fischer, P.C., The reduction of tape reversals for off-line one-tape Turing machines, J. computer syst. sci., 2, 136-147, (1968) · Zbl 0199.31001
[17] Ginsburg, S., ()
[18] Ginsburg, S.; Spanier, E.H., SIAM J. control, 4, 429-543, (1966)
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.