×

zbMATH — the first resource for mathematics

Reversal-bounded multipushdown machines. (English) Zbl 0309.68043

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
Full Text: DOI
References:
[1] \scB. Baker, On finding “small” integer solutions to sets of linear equations, submitted for publication.
[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, (), 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., ()
[6] Ginsburg, S.; Goldstine, J., Intersection-closed full AFL and the recursively enumerable languages, (), 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, (), 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, ()
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.