{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:53:11Z","timestamp":1725663191643},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514862"},{"type":"electronic","value":"9783540481768"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51486-4_56","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:59:07Z","timestamp":1330203547000},"page":"49-66","source":"Crossref","is-referenced-by-count":4,"title":["Space bounded computations : Review and new separation results"],"prefix":"10.1007","author":[{"given":"J.","family":"Hartmanis","sequence":"first","affiliation":[]},{"given":"Desh","family":"Ranjan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/S0022-0000(75)80052-3","volume":"11","author":"A. R. Freedman","year":"1975","unstructured":"A.R. Freedman and R.E. Ladner. Space bounds for processing counterless inputs. Journal of Computer and System Sciences, 11:118\u2013128, 1975.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR2","first-page":"158","volume":"23","author":"R. Freivalds","year":"1979","unstructured":"R. Freivalds. On the worktime of deterministic and non-deterministic turing machines. Latvijskij Matematiceskij Eshegodnik, 23:158\u2013165, 1979.","journal-title":"Latvijskij Matematiceskij Eshegodnik"},{"key":"4_CR3","first-page":"82","volume":"35","author":"J. Hartmanis","year":"1988","unstructured":"J. Hartmanis, R. Chang, J. Kadin, and S. Mitchell. Some observations about space bounded computations. Bulletin of the EATCS, 35:82\u201392, June 1988.","journal-title":"Bulletin of the EATCS"},{"key":"4_CR4","first-page":"1","volume":"7","author":"J. Hartmanis","year":"1974","unstructured":"J. Hartmanis and H.H. Hunt. On the LBA problem and its importance in the theory of computation. SIAM-AMS, 7:1\u201326, 1974.","journal-title":"SIAM-AMS"},{"key":"4_CR5","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automats Theory, Languages and Computation. Addison-Wesley Publishing Company, 1979."},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Neil Immerman. Nondeterministic space is closed under complement. In Proceedings of Structure in Complexity Theory Third Annual Conference, pages 112\u2013115. Computer Society of IEEE, 1988.","DOI":"10.1109\/SCT.1988.5270"},{"key":"4_CR7","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0019-9958(64)90120-2","volume":"7","author":"S. Y. Kuroda","year":"1964","unstructured":"S.Y. Kuroda. Classes of languages and linearly-bounded automata. Information and Control, 7:207\u2013223, 1964.","journal-title":"Information and Control"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"P.M. Lewis II, R.E. Stearns, and J. Hartmanis. Memory bounds for recognition of context-free and context-sensitive languages. In IEEE Conference Record on Switching Circuit Theory and Logic Design, pages 191\u2013202, 1965.","DOI":"10.1109\/FOCS.1965.14"},{"key":"4_CR9","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"W.J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4:177\u2013192, 1970.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR10","unstructured":"Seiferas. A note on notions of tape constructibility. Technical Report CSD-TR 187, Pennsylvania State University, 1976."},{"key":"4_CR11","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","volume":"10","author":"M. Sipser","year":"1980","unstructured":"M. Sipser. Halting space-bounded computations. Theoretical Computer Science, 10:335\u2013338, 1980.","journal-title":"Theoretical Computer Science"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"R.E. Stearns, J. Hartmanis, and P.M. Lewis II. Heirarchies of memory limited computations. In 1965 IEEE Conference Record on Switching Circuit Theory and Logical Design, pages 179\u2013190, 1965.","DOI":"10.1109\/FOCS.1965.11"},{"key":"4_CR13","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"R. Szelepcs\u00e9nyi. The method of forcing for nondeterministic automata. The Bulletin of the European Association for Theoretical Computer Science, 33:96\u2013100, October 1987.","journal-title":"The Bulletin of the European Association for Theoretical Computer Science"},{"key":"4_CR14","unstructured":"A. Szepietowski. Some notes on strong and weak log log n space complexity. Technical report, Mathematical Department, Technical University of Gda \u0144sk, Majakowskiego 11\/12, PL-80-952 Gda\u0144sk, Poland, 1988."},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"A. Szepietowski. If deterministic and nondeterministic space complexity are equal for log log n then they are equal for log n. In Lecture Notes in Computer Science, volume 349, pages 251\u2013255. Springer-Verlag, 1989. STACS '89.","DOI":"10.1007\/BFb0028989"},{"key":"4_CR16","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. B. Wilson","year":"1985","unstructured":"C.B. Wilson. Relativized circuit complexity. Journal of Computer and System Sciences, 31:169\u2013181, 1985.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/3-540-16486-3_111","volume":"223","author":"C. B. Wilson","year":"1986","unstructured":"C.B. Wilson. Parallel computation and the NC heirarchy relativized. In Lecture Notes in Computer Science, volume 223, pages 362\u2013382. Springer-Verlag, 1986. Structure in Complexity Theory.","journal-title":"Lecture Notes in Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1989"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51486-4_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:21:19Z","timestamp":1605648079000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51486-4_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514862","9783540481768"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-51486-4_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}