{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:48:58Z","timestamp":1725662938728},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540164869"},{"type":"electronic","value":"9783540398257"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_86","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:45:40Z","timestamp":1330195540000},"page":"12-22","source":"Crossref","is-referenced-by-count":6,"title":["Isomorphisms and 1-L reductions"],"prefix":"10.1007","author":[{"given":"Eric W.","family":"Allender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"2_CR1","unstructured":"E. W. Allender, Invertible functions, Doctoral Dissertation, Georgia Institute of Technology."},{"key":"2_CR2","unstructured":"E. W. Allender, The complexity of sparse sets in P, These Proceedings."},{"key":"2_CR3","unstructured":"L. Berman, Polynomial reducibilities and complete sets, Doctoral Dissertation, Cornell University."},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"L. Berman and J. Hartmanis, On isomorphisms and density of NP and other complete sets, SIAM J. Comput. 6, 305\u2013323.","DOI":"10.1137\/0206023"},{"key":"2_CR5","unstructured":"M. Dowd, Isomorphism of complete sets, Technical Report LCSR-TR-34, Rutgers University."},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, N. Immerman, and S. Mahaney, One-way log-tape reductions, Proc. 19th IEEE Symposium on Foundations of Computer Science, pp. 65\u201372.","DOI":"10.1109\/SFCS.1978.31"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"J. Hartmanis and S. Mahaney, Languages simultaneously complete for one-way and two-way log-tape automata, SIAM J. Comput. 10, 383\u2013390.","DOI":"10.1137\/0210027"},{"key":"2_CR8","unstructured":"J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass."},{"key":"2_CR9","unstructured":"D. T. Huynh, Non-uniform complexity and the randomness of certain complete languages, Technical Report TR 85-34, Computer Science Department, Iowa State University."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"D. Joseph and P. Young, Some remarks on witness functions for non-polynomial and non-complete sets in NP, Theoretical Computer Science 39, 225\u2013237.","DOI":"10.1016\/0304-3975(85)90140-9"},{"key":"2_CR11","unstructured":"K.-I. Ko, T. J. Long, and D.-Z. Du, A note on one-way functions and polynomial-time isomorphisms, to appear."},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"S. Mahaney and P. Young, Reductions among polynomial isomorphism types, Theoretical Computer Science 39, 207\u2013224.","DOI":"10.1016\/0304-3975(85)90139-2"},{"key":"2_CR13","unstructured":"L. J. Stockmeyer, The complexity of decision problems in automata theory and logic, Doctoral Dissertation, M.I.T."},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Osamu Watanabe, On one-one polynomial time equivalence relations, Theoretical Computer Science 38, 157\u2013165.","DOI":"10.1016\/0304-3975(85)90218-X"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_86.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:04:18Z","timestamp":1619557458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_86"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_86","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}