{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:52:52Z","timestamp":1725663172390},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540100034"},{"type":"electronic","value":"9783540393467"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1980]]},"DOI":"10.1007\/3-540-10003-2_85","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T12:00:21Z","timestamp":1330171221000},"page":"374-384","source":"Crossref","is-referenced-by-count":7,"title":["Symmertric space-bounded computation (extended abstract)"],"prefix":"10.1007","author":[{"given":"Harry R.","family":"Lewis","sequence":"first","affiliation":[]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, C. Rackoff: Random walks, universal sequences, and the complexity of maze problems, Proceedings of 20th Annual Symposium on Foundations of Computer Science, 1979, pp. 218\u2013223.","DOI":"10.1109\/SFCS.1979.34"},{"key":"32_CR2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. A. Cook","year":"1971","unstructured":"S.A. Cook: Characterizations of pushdown machines in terms of time-bounded computers, Journal of the Association for Computing Machinery 18 (1971), pp. 4\u201318.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"32_CR3","doi-asserted-by":"crossref","unstructured":"A. Cypher: An approach to the k-paths problem, Proceedings of 12th Annual Symposium on Theory of Computing, 1980.","DOI":"10.1145\/800141.804668"},{"key":"32_CR4","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"S. Fortune, J.E. Hopcroft, J. Wyllis: The directed subgraph homeomorphism problem, Theoretical Computer Science 10 (1980), pp. 111\u2013121.","journal-title":"Theoretical Computer Science"},{"key":"32_CR5","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill: Computational complexity of probabilistic Turing machines, SIAM Journal on Computing 6 (1977), pp. 675\u2013695.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR6","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"J. D. Hopcroft","year":"1971","unstructured":"J.D. Hopcroft, J.E. Ullman: Nonerasing stack automata, Journal of the Association for Computing Machinery 18 (1971), pp. 4\u201318.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"32_CR7","unstructured":"J.D. Hopcroft, J.E. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979."},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"H. Jia-wei: On some deterministic space complexity problems, Proceedings of 12th Annual Symposium on Theory of Computing, 1980.","DOI":"10.1145\/800141.804679"},{"key":"32_CR9","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. D. Jones","year":"1972","unstructured":"N.D. Jones: Space-bounded reducibility among combinatorial problems, Journal of Computer and Systems Sciences 11 (1972), pp. 68\u201385.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"32_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"N. D. Jones","year":"1976","unstructured":"N.D. Jones, Y.E. Lien, W.T. Laaser: New problems complete for log space, Mathematical Systems Theory 10 (1976), pp. 1\u201317.","journal-title":"Mathematical Systems Theory"},{"key":"32_CR11","unstructured":"A. LaPaugh: Private communication, November 1979."},{"key":"32_CR12","doi-asserted-by":"crossref","unstructured":"A. LaPaugh, R.L. Rivest: The subgraph homeomorphism problem, Proceedings of 10th Annual Symposium on Theory of Computing, 1978, pp. 40\u201350.","DOI":"10.1145\/800133.804330"},{"key":"32_CR13","unstructured":"H.R. Lewis, C.H. Papadimitriou: Elements of the Theory of Computation, Prentice-Hall, 1981 (to appear)."},{"key":"32_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2267170","volume":"13","author":"E. L. Post","year":"1947","unstructured":"E.L. Post: Recursive unsolvability of a problem of Thue, Journal of Symbolic Logic 13 (1947), pp. 1\u201311.","journal-title":"Journal of Symbolic Logic"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"S. Ruby and P.C. Fischer: Translational methods and computational complexity, IEEE Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 173\u2013178.","DOI":"10.1109\/FOCS.1965.33"},{"key":"32_CR16","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: Relations between nondeterministic and deterministic tape complexities, Journal of Computer and Systems Sciences 4 (1970), pp. 177\u2013192.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"32_CR17","unstructured":"Y. Shiloach: The two paths problem is polynomial, Journal of the Association for Computing Machinery, to appear."},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"W.J. Sakoda, M. Sipser: Nondeterminism and the size of two-way finite automata, Proceedings of 10th Annual Symposium on Theory of Computing, 1978, pp. 275\u2013286.","DOI":"10.1145\/800133.804357"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"M. Sipser: Lower bounds on the size of sweeping automata, Proceedings of 11th Annual Symposium on Theory of Computing, 1979, pp. 360\u2013364.","DOI":"10.1145\/800135.804429"}],"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-10003-2_85.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T16:33:13Z","timestamp":1619541193000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10003-2_85"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1980]]},"ISBN":["9783540100034","9783540393467"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-10003-2_85","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1980]]}}}