×
Baker, Brenda S.; Book, Ronald V.

Reversal-bounded multipushdown machines. (English) Zbl 0309.68043

J. Comput. Syst. Sci. 8, 315-332 (1974).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0309.68043

Cited in 1 Review
Cited in 105 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
03D25 Recursively (computably) enumerable sets and degrees
03D10 Turing machines and related notions
PDF BibTeX XML Cite
\textit{B. S. Baker} and \textit{R. V. Book}, J. Comput. Syst. Sci. 8, 315--332 (1974; Zbl 0309.68043)
Full Text: DOI

References:

[2] Book, R., On languages accepted in polynomial time, SIAM J. Computing, 1, 281-287 (1972) · Zbl 0251.68042
[3] Chomsky, N.; Schutzenberger, M., The algebraic theory of context-free languages, (Braffort; Hirschberg, Computer Programming and Formal Systems (1967), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam), 118-161 · Zbl 0148.00804
[4] Fischer, P., The reduction of tape reversals for off-line one-tape Turing machines, J. Comput. System Sci., 2, 136-147 (1968) · Zbl 0199.31001
[5] Ginsburg, S., (The Mathematical Theory of Contex-free Languages (1966), McGraw-Hill) · Zbl 0184.28401
[6] Ginsburg, S.; Goldstine, J., Intersection-closed full AFL and the recursively enumerable languages, (Proceedings of the Third ACM Symposium on Theory of Computing (1971)), 121-131 · Zbl 0251.68044
[7] Ginsburg, S.; Greibach, S., Abstract families of languages, Mem. Amer. Math. Soc., 87, 1-32 (1969) · Zbl 0194.31402
[8] Ginsburg, S.; Greibach, S., Principal AFL, J. Comput. System Sci., 4, 308-338 (1970) · Zbl 0198.03102
[9] Ginsburg, S.; Greibach, S.; Harrison, M., One-way stack automata, J. Assoc. Comput. Mach., 14, 389-418 (1967) · Zbl 0171.14803
[10] Ginsburg, S.; Spanier, E., Finite-turn pushdown automata, SIAM J. Control, 4, 429-453 (1966) · Zbl 0147.25302
[11] Greibach, S., A note on undecidable properties of formal languages, Math. Systems Theory, 2, 1-6 (1968) · Zbl 0157.01902
[12] Greibach, S., An infinite hierarchy of context-free languages, J. Assoc. Comput. Mach., 16, 91-106 (1969) · Zbl 0182.02002
[13] Greibach, S., The hardest context-free language, SIAM J. Computing, 2, 304-310 (1973) · Zbl 0278.68073
[14] Greibach, S.; Ginsburg, S., Multi-tape AFA, J. Assoc. Comput. Mach., 19, 192-221 (1972)
[15] Hartmanis, J., Context-free languages and Turing machine computations, (Proc. Symp. Applied Math., 19 (1967)), 42-51 · Zbl 0189.29101
[16] Hartmanis, J., Tape-reversal bounded Turing machine computations, J. Comput. System Sci., 2, 117-135 (1968) · Zbl 0259.68020
[17] Hartmanis, J.; Hopcroft, J., What makes some language theory problems undecidable, J. Comput. System Sci., 3, 196-217 (1969) · Zbl 0231.68031
[18] Kameda, T.; Vollmar, R., Note on tape reversal complexity of languages, Information and Control, 17, 203-215 (1970) · Zbl 0196.01801
[19] Savitch, W., Normal form theorems for phrase structure grammars, (Proceedings of the 6th Princeton Conference on Information Science and Systems (1972))
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.