{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:01Z","timestamp":1725663241017},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540083429"},{"type":"electronic","value":"9783540373056"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1977]]},"DOI":"10.1007\/3-540-08342-1_9","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:23:54Z","timestamp":1330187034000},"page":"111-119","source":"Crossref","is-referenced-by-count":1,"title":["On the computational power of reversal-bounded machines"],"prefix":"10.1007","author":[{"given":"Ronald V.","family":"Book","sequence":"first","affiliation":[]},{"given":"Chee K.","family":"Yap","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"9_CR1","first-page":"315","volume":"8","author":"B. Baker","year":"1974","unstructured":"B. Baker and R. Book, Reversal-bounded multipushdown machines, JCSS 8 (1974), 315\u2013322.","journal-title":"JCSS"},{"key":"9_CR2","unstructured":"R. Book, Simple representations of certain classes of languages, submitted for publication."},{"key":"9_CR3","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01705890","volume":"4","author":"R. Book","year":"1970","unstructured":"R. Book and S. Greibach, Quasi-realtime languages, Math. Systems Theory 4 (1970), 97\u2013111.","journal-title":"Math. Systems Theory"},{"key":"9_CR4","unstructured":"R. Book and M. Nivat, Linear languages and intersections of classes of languages, in preparation."},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1137\/0203023","volume":"3","author":"R. Book","year":"1974","unstructured":"R. Book, M. Nivat, and M. Paterson, Reversal-bounded acceptors and intersections of linear languages, SIAM J. Computing 3 (1974), 283\u2013295.","journal-title":"SIAM J. Computing"},{"key":"9_CR6","first-page":"136","volume":"2","author":"P. Fischer","year":"1968","unstructured":"P. Fischer, The reduction of tape reversals for off-line one-tape Turing machines, JCSS 2 (1968), 136\u2013147.","journal-title":"JCSS"},{"key":"9_CR7","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1145\/321724.321726","volume":"19","author":"P. Fischer","year":"1972","unstructured":"P. Fischer, A. Meyer, and A. Rosenberg, Real-time simulation of multihead tape units, JACM 19 (1972), 590\u2013607.","journal-title":"JACM"},{"key":"9_CR8","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1137\/0304034","volume":"4","author":"S. Ginsburg","year":"1966","unstructured":"S. Ginsburg and E. Spanier, Finite-turn pushdown machines, SIAM J. Control 4 (1966), 429\u2013453.","journal-title":"SIAM J. Control"},{"key":"9_CR9","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/321495.321503","volume":"16","author":"S. Greibach","year":"1969","unstructured":"S. Greibach, An infinite hierarchy of context-free languages, JACM 16 (1969), 91\u2013106.","journal-title":"JACM"},{"key":"9_CR10","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0304-3975(76)90072-4","volume":"1","author":"S. Greibach","year":"1976","unstructured":"S. Greibach, Remarks on the complexity of nondeterministic counter languages, Theoretical Computer Science 1 (1976), 269\u2013288.","journal-title":"Theoretical Computer Science"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"S. Greibach, Visits, crosses and reversals for nondeterministic off-line machines, Info. Control, to appear.","DOI":"10.1016\/S0019-9958(78)90289-9"},{"key":"9_CR12","first-page":"117","volume":"2","author":"J. Hartmanis","year":"1968","unstructured":"J. Hartmanis, Tape-reversal bounded Turing machine computations, JCSS 2 (1968), 117\u2013135.","journal-title":"JCSS"},{"key":"9_CR13","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis and R. Stearns, On the computational complexity of algorithms, Trans. Amer. Math. Soc. 117 (1965), 285\u2013306.","journal-title":"Trans. Amer. Math. Soc."},{"key":"9_CR14","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0019-9958(70)90549-8","volume":"17","author":"T. Kameda","year":"1970","unstructured":"T. Kameda and R. Vollmar, Note on tape reversal complexity of languages, Info. Control 17 (1970), 203\u2013215.","journal-title":"Info. Control"},{"key":"9_CR15","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1145\/321420.321423","volume":"14","author":"A. Rosenberg","year":"1967","unstructured":"A. Rosenberg, Real-time definable languages, JACM 14 (1967), 645\u2013662.","journal-title":"JACM"},{"key":"9_CR16","unstructured":"R. Schroeppel, A two counter machine cannot calculate 2n, M.I.T. AI Memo. 257 (1973)."},{"key":"9_CR17","unstructured":"F. Yao, Computation by 2-counter machines, unpublished paper."},{"key":"9_CR18","first-page":"564","volume":"4","author":"A. Barashka","year":"1975","unstructured":"A. Barashka, Concerning the number of reversals of the stack head of a two-way pushdown automaton, Cybernetics 4 (1975), 564\u2013570.","journal-title":"Cybernetics"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"R. Book, On languages with a certain prefix property, Math. Systems Theory 10 (1977), to appear.","DOI":"10.1007\/BF01683274"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08342-1_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:59:17Z","timestamp":1605643157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08342-1_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540083429","9783540373056"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-08342-1_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1977]]}}}