{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:47:46Z","timestamp":1725662866272},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540088608"},{"type":"electronic","value":"9783540358077"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1978]]},"DOI":"10.1007\/3-540-08860-1_22","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:34:33Z","timestamp":1330187673000},"page":"300-321","source":"Crossref","is-referenced-by-count":9,"title":["A pspace complete problem related to a pebble game"],"prefix":"10.1007","author":[{"given":"Andrzej","family":"Lingas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"22_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman \/1974\/, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading Mass."},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"A.V.Aho and R.Sethi \/1977\/, How hard is compiler code generation? in: Proc. Fourth Colloquium on Automata Languages and Programming, pp. 1\u201315, Lecture Notes in Computer Science 52, Springer \/1977\/.","DOI":"10.1007\/3-540-08342-1_1"},{"key":"22_CR3","unstructured":"S.Even and R.E.Tarjan, A.Combinatorial problem which is complete in polynomial space."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"J.E.Hopcroft, W.J.Paul and L.G.Valiant \/1975\/, On time versus space and related problems, Proc.16 th Annual Symposium on Fundations of Computer Science, pp.57\u201364.","DOI":"10.1109\/SFCS.1975.23"},{"issue":"1","key":"22_CR5","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BF01683259","volume":"10","author":"N. D. Jones","year":"1976","unstructured":"N.D. Jones, Y.E. Lien, W.T. Laaser \/1976\/, New problem complete for nondeterministic log-space, Mathematical Systems Theory 10:1, 239\u2013259.","journal-title":"Mathematical Systems Theory"},{"issue":"3","key":"22_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"W. J. Paul","year":"1976","unstructured":"W.J. Paul, R.E. Tarjan, J.R. Celoni \/1976\/77\/, Space bounds for a game on graphs, Mathematical Systems Theory, 10:3, 1\u201317.","journal-title":"Mathematical Systems Theory"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"W.J.Paul, R.E.Tarjan \/1977\/, Time-space trade offs in a pebble game, in: Proc.Fourth Colloquium on Automata Languages and Programing, pp.365\u2013369, Lecture Notes in Computer Science, Springer \/1977\/.","DOI":"10.1007\/3-540-08342-1_28"},{"issue":"2","key":"22_CR8","first-page":"177","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"W.J. Savitch \/1970\/, Relationships between nondeterministic and deterministic complexities, JCSS 4:2, 177\u2013192.","journal-title":"JCSS"},{"issue":"3","key":"22_CR9","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1137\/0204020","volume":"4","author":"R. Sethi","year":"1975","unstructured":"R. Sethi \/1975\/, Complete register allocation problems, SIAM J.Computing 4:3, 226\u2013248.","journal-title":"SIAM J.Computing"},{"issue":"3","key":"22_CR10","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1145\/321650.321653","volume":"18","author":"R. Simon","year":"1971","unstructured":"R. Simon and R.C.T. Lee \/1971\/, On the optimal solution to AND\/OR series-parallel praphs, J.ACM 18:3, 354\u2013372.","journal-title":"J.ACM"},{"issue":"1","key":"22_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"E. Stockmeyer","year":"1977","unstructured":"E. Stockmeyer \/1977\/, The polynomial-time hierarchy, Theoretical Computer Science, 3:1, 1\u201322.","journal-title":"Theoretical Computer Science"}],"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-08860-1_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:00:03Z","timestamp":1605643203000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08860-1_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1978]]},"ISBN":["9783540088608","9783540358077"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-08860-1_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1978]]}}}