{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:11Z","timestamp":1725663611866},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540551218"},{"type":"electronic","value":"9783540467359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55121-2_19","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T09:47:22Z","timestamp":1330249642000},"page":"198-208","source":"Crossref","is-referenced-by-count":0,"title":["Complete problems for logspace involving lexicographic first paths in graphs"],"prefix":"10.1007","author":[{"given":"Iain A.","family":"Stewart","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(87)90105-0","volume":"24","author":"R. Anderson","year":"1987","unstructured":"R.ANDERSON and E.W.MAYR, Parallelism and the maximal path problem, Inform. Process. Lett. 24 (1987), 121\u2013126.","journal-title":"Inform. Process. Lett."},{"key":"19_CR2","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D.A.M. Barrington","year":"1990","unstructured":"D.A.M.BARRINGTON, N.IMMERMAN and H.STRAUBING, On uniformity within NC 1, J. Comput. System Sci. 41 (1990), 274\u2013306.","journal-title":"J. Comput. System Sci."},{"key":"19_CR3","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S.A. Cook","year":"1987","unstructured":"S.A.COOK and P.MCKENZIE, Problems complete for deterministic logarithmic space, J. Algorithms 8 (1987), 385\u2013394.","journal-title":"J. Algorithms"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"S.A.COOK, A taxonomy of problems with fast parallel algorithms, Inform. and Control 64 (1985), 2\u201322.","journal-title":"Inform. and Control"},{"key":"19_CR5","unstructured":"R.GREENLAW, H.J.HOOVER and W.L.RUZZO, A compendium of problems complete for P, Part II: P-complete problems, Tech. Rep., University of Alberta, to appear."},{"key":"19_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R.GAREY and D.S.JOHNSON, \u201cComputers and Intractability: A Guide to the Theory of NP-completeness\u201d, Freeman, San Francisco, 1979."},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"N.IMMERMAN and S.LANDAU, The complexity of iterated multiplication, in \u201cProc. 4th Symp. on Structure in Complexity Theory, 1989\u201d, 104\u2013111.","DOI":"10.1109\/SCT.1989.41816"},{"issue":"No.4","key":"19_CR8","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N.IMMERMAN, Languages which capture complexity classes, SIAM J. Comput. 16, No.4 (1987), 760\u2013778.","journal-title":"SIAM J. Comput."},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"N.IMMERMAN, Expressibility as a complexity measure: Results and directions, in \u201cProc. 2nd Symp. on Structure in Complexity Theory, 1987\u201d, 194\u2013202.","DOI":"10.1109\/PSCT.1987.10319271"},{"issue":"No.5","key":"19_CR10","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N.IMMERMAN, Non deterministic space is closed under complementation, SIAM J. Comput. 17, No.5 (1988), 935\u2013938.","journal-title":"SIAM J. Comput."},{"issue":"No.1","key":"19_CR11","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02088292","volume":"22","author":"S. Miyano","year":"1989","unstructured":"S.MIYANO, The lexicographically first maximal subgraph problems: P-completeness and NC algorithms, Math. Systems Theory 22, No.1 (1989), 47\u201373.","journal-title":"Math. Systems Theory"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"I.A.STEWART, Using the Hamiltonian path operator to capture NP, extended abstract in \u201cProc. 2nd International Conference on Computing and Information, 1990\u201d, Lecture Notes in Computer Science Vol. 468, Springer-Verlag, 134-143: to appear, J. Comput. System Sci.","DOI":"10.1007\/3-540-53504-7_70"},{"issue":"No.3","key":"19_CR13","first-page":"305","volume":"1","author":"I.A. Stewart","year":"1991","unstructured":"I.A.STEWART, Comparing the expressibility of languages formed using NP-complete operators, extended abstract in \u201cProc. 16th International Workshop on Graph Theoretic concepts in Computer Science, 1990\u201d: J. Logic and Computation 1, No. 3 (1991), 305\u2013330.","journal-title":"\u201cProc. 16th International Workshop on Graph Theoretic concepts in Computer Science, 1990\u201d: J. Logic and Computation"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55121-2_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T14:20:33Z","timestamp":1713622833000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55121-2_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540551218","9783540467359"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-55121-2_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}