×

zbMATH — the first resource for mathematics

Time- and tape-bounded Turing acceptors and AFLs. (English) Zbl 0206.28702

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Book, R., Grammars with time functions, (), Also appears as Mathematical Linguistics and Automatic Translation, Report No. NSF-23, Aiken Computation Laboratory, Harvard University, 1969
[2] Book, R.; Greibach, S., Quasirealtime languages, Math. systems theory, 4, 97-111, (1970) · Zbl 0188.33102
[3] Ginsburg, S.; Greibach, S., Abstract families of languages, Amer. math. soc. mem., No. 87, 1-32, (1969) · Zbl 0194.31402
[4] Ginsburg, S.; Greibach, S., Principal AFL, SDC technical report, (1969)
[5] Ginsburg, S.; Greibach, S.; Hopcroft, J., Pre-AFL, Amer. math. soc. mem., No. 87, 33-40, (1969)
[6] Ginsburg, S.; Hopcroft, J., Images of AFL under certain families of homomorphisms, SDC technical report, (1969)
[7] Greibach, S.; Hopcroft, J., Independence of AFL operations, Amer. math. soc. mem., No. 87, 41-51, (1969) · Zbl 0194.31402
[8] Hartmanis, J.; Stearns, R., On the computation complexity of algorithms, Trans. amer. math. soc., 385-406, (1965) · Zbl 0131.15404
[9] Hartmanis, J.; Stearns, R., Automata-based computational complexity, Information sciences, 1, 173-184, (1969)
[10] Hopcroft, J.; Ullman, J., An approach to a unified theory of automata, Bell system tech. J., 46, 1763-1829, (1967) · Zbl 0155.34303
[11] Hopcroft, J.; Ullman, J., ()
[12] Hopcroft, J.; Ullman, J., Some results on tape-bounded Turing machines, J. assoc. comput. Mach., 16, 168-177, (1969) · Zbl 0188.33501
[13] {\scP. M. Lewis, II, R. Stearns, and J. Hartmanis}, Memory bounds for recognition or context-free and context0sensitive languages, 1965 IEEE Conference Record on Switching Circuit Theory and Logical Design, 191-202.
[14] Rosenberg, A.L., Real-time definable languages, J. assoc. comput. Mach., 14, 645-662, (1967) · Zbl 0153.00902
[15] Savitch, W., Relationships between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
[16] {\scR. Stearns, J. Hartmanis, and P. M. Lewis, II}, Hierarchies of memory limited computations, 1965 IEEE Conference Record on Switching Circuit Theory and Logical Design, 179-190 · Zbl 0229.02033
[17] Wegbreit, B., A generator of context-sensitive languages, J. comput. system sci., 3, 456-462, (1969) · Zbl 0205.31302
[18] Yamada, H., Real-time computation and recursive functions not real-time computable, IEEE trans. electron. comput., 11, 753-760, (1962) · Zbl 0124.25006
[19] Young, P.R., Toward a theory of enumeration, J. assoc. computing Mach., 16, 328-348, (1969) · Zbl 0191.30801
[20] Book, R.; Greibach, S.; Ibarra, O.; Wegbreit, B., Tape-bounded Turing acceptors and principal afls, J. comput. system sciences, 4, 622-625, (1970) · Zbl 0206.28703
[21] Cook, S., Variations on pushdown machines, (), 229-230 · Zbl 1282.68103
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.