×

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


MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Book, R., Grammars with time functions, (Ph.D. thesis (1969), Harvard University), 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) · Zbl 0194.31402
[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., (Formal Languages and their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass.) · Zbl 0196.01701
[12] Hopcroft, J.; Ullman, J., Some results on tape-bounded Turing machines, J. Assoc. Comput. Mach., 16, 168-177 (1969) · Zbl 0188.33501
[13] P. M. Lewis, II, R. Stearns, and J. Hartmanis1965 IEEE Conference Record on Switching Circuit Theory and Logical Design; P. M. Lewis, II, R. Stearns, and J. Hartmanis1965 IEEE Conference Record on Switching Circuit Theory and Logical Design
[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] R. Stearns, J. Hartmanis, and P. M. Lewis, II1965 IEEE Conference Record on Switching Circuit Theory and Logical Design; R. Stearns, J. Hartmanis, and P. M. Lewis, II1965 IEEE Conference Record on Switching Circuit Theory and Logical Design · 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, (Proc. First ACM Symposium on Theory of Computing (May, 1969)), 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. 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.