This research was supported in part by the National Science Foundation under Grant MCS-76-05744.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
B. Baker and R. Book, Reversal-bounded multipushdown machines, JCSS 8 (1974), 315–322.
R. Book, Simple representations of certain classes of languages, submitted for publication.
R. Book and S. Greibach, Quasi-realtime languages, Math. Systems Theory 4 (1970), 97–111.
R. Book and M. Nivat, Linear languages and intersections of classes of languages, in preparation.
R. Book, M. Nivat, and M. Paterson, Reversal-bounded acceptors and intersections of linear languages, SIAM J. Computing 3 (1974), 283–295.
P. Fischer, The reduction of tape reversals for off-line one-tape Turing machines, JCSS 2 (1968), 136–147.
P. Fischer, A. Meyer, and A. Rosenberg, Real-time simulation of multihead tape units, JACM 19 (1972), 590–607.
S. Ginsburg and E. Spanier, Finite-turn pushdown machines, SIAM J. Control 4 (1966), 429–453.
S. Greibach, An infinite hierarchy of context-free languages, JACM 16 (1969), 91–106.
S. Greibach, Remarks on the complexity of nondeterministic counter languages, Theoretical Computer Science 1 (1976), 269–288.
S. Greibach, Visits, crosses and reversals for nondeterministic off-line machines, Info. Control, to appear.
J. Hartmanis, Tape-reversal bounded Turing machine computations, JCSS 2 (1968), 117–135.
J. Hartmanis and R. Stearns, On the computational complexity of algorithms, Trans. Amer. Math. Soc. 117 (1965), 285–306.
T. Kameda and R. Vollmar, Note on tape reversal complexity of languages, Info. Control 17 (1970), 203–215.
A. Rosenberg, Real-time definable languages, JACM 14 (1967), 645–662.
R. Schroeppel, A two counter machine cannot calculate 2n, M.I.T. AI Memo. 257 (1973).
F. Yao, Computation by 2-counter machines, unpublished paper.
A. Barashka, Concerning the number of reversals of the stack head of a two-way pushdown automaton, Cybernetics 4 (1975), 564–570.
R. Book, On languages with a certain prefix property, Math. Systems Theory 10 (1977), to appear.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1977 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Book, R.V., Yap, C.K. (1977). On the computational power of reversal-bounded machines. In: Salomaa, A., Steinby, M. (eds) Automata, Languages and Programming. ICALP 1977. Lecture Notes in Computer Science, vol 52. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-08342-1_9
Download citation
DOI: https://doi.org/10.1007/3-540-08342-1_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-08342-9
Online ISBN: 978-3-540-37305-6
eBook Packages: Springer Book Archive