{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:18Z","timestamp":1742617158763,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_19","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:13:56Z","timestamp":1330254836000},"page":"163-174","source":"Crossref","is-referenced-by-count":9,"title":["A first-order isomorphism theorem"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"Jose","family":"Balc\u00e1zar","sequence":"additional","affiliation":[]},{"given":"Neil","family":"Immerman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"19_CR1","unstructured":"Manindra Agrawal and Somenath Biswas, \u201cPolynomial Isomorphism of 1-L-Complete Sets,\u201d manuscript, 1992."},{"key":"19_CR2","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1016\/0022-0000(88)90033-5","volume":"36","author":"E. Allender","year":"1988","unstructured":"Eric Allender, \u201cIsomorphisms and 1-L Reductions,\u201d J. Computer Sys. Sci. 36 (1988), 336\u2013350.","journal-title":"J. Computer Sys. Sci."},{"key":"19_CR3","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1145\/76359.76370","volume":"36","author":"E. Allender","year":"1989","unstructured":"Eric Allender, \u201cP-Uniform Circuit Complexity,\u201d JACM 36 (1989), 912\u2013928.","journal-title":"JACM"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Eric Allender and Vivek Gore, \u201cA Uniform Circuit Lower Bound for the Permanent,\u201d DIMACS Tech Report 92-30. A preliminary version appeared as \u201cOn Strong Separations from AC0,\u201d Proc. FCT '91, Lecture Notes in Computer Science 529, Springer-Verlag, 1991, 1\u201315.","DOI":"10.1007\/3-540-54458-5_44"},{"key":"19_CR5","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. Barrington","year":"1990","unstructured":"D. Barrington, N. Immerman, H. Straubing, \u201cOn Uniformity Within NC1,\u201d J. Computer Sys. Sci. 41 (1990), 274\u2013306.","journal-title":"J. Computer Sys. Sci."},{"key":"19_CR6","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Len Berman and Juris Hartmanis, \u201cOn Isomorphism and Density of NP and Other Complete Sets,\u201d SIAM J. Comput. 6 (1977), 305\u2013322.","journal-title":"SIAM J. Comput."},{"key":"19_CR7","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/0890-5401(87)90022-8","volume":"74","author":"R. Boppana","year":"1987","unstructured":"Ravi Boppana and Jeff Lagarias, \u201cOne-Way Functions and Circuit Complexity,\u201d Information and Computation 74, (1987), 226\u2013240.","journal-title":"Information and Computation"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Hans-J\u00f6rg Burtschick and Albrecht Hoene, \u201cThe degree structure of 1-L reductions,\u201d Proc. Math. Foundations of Computer Science, Lecture Notes in Computer Science 629, Springer-Verlag, 1992, 153\u2013161.","DOI":"10.1007\/3-540-55808-X_13"},{"key":"19_CR9","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"Ashok Chandra, Larry Stockmeyer, and Uzi Vishkin, \u201cConstant Depth Reducibility,\u201d SIAM J. Comput. 13, (1984), 423\u2013439.","journal-title":"SIAM J. Comput."},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Stephen Cook, \u201cThe Complexity of Theorem Proving Procedures,\u201d Proc. Third Annual ACM STOC Symp. (1971), 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Elias Dahlhaus, \u201cReduction to NP-Complete Problems by Interpretations,\u201d in Logic and Machines: Decision Problems and Complexity, B\u00f6rger, R\u00f6dding, and Hasenjaeger eds., Lecture Notes In Computer Science 171, Springer-Verlag, 1984, 357\u2013365.","DOI":"10.1007\/3-540-13331-3_51"},{"key":"19_CR12","unstructured":"Herbert Enderton, A Mathematical Introduction to Logic, Academic Press, 1972."},{"key":"19_CR13","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"Merrick Furst, James Saxe, and Michael Sipser, \u201cParity, Circuits, and the Polynomial-Time Hierarchy,\u201d Math. Systems Theory 17 (1984), 13\u201327.","journal-title":"Math. Systems Theory"},{"key":"19_CR14","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability, Freeman, 1979."},{"key":"19_CR15","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0020-0190(87)90053-6","volume":"26","author":"J. Hastad","year":"1987","unstructured":"Johan Hastad, \u201cOne-Way Permutations in NC0,\u201d Information Processing Letters 26 (1987), 153\u2013155.","journal-title":"Information Processing Letters"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Juris Hartmanis, Neil Immerman, and Stephen Mahaney, \u201cOne-Way Log Tape Reductions,\u201d 19th IEEE FOCS Symp. (1978), 65\u201372.","DOI":"10.1109\/SFCS.1978.31"},{"key":"19_CR17","unstructured":"L. Hemachandra and A. Hoene, \u201cCollapsing Degrees Via Strong Computation,\u201d to appear in J. of Computer Sys. Sci.."},{"key":"19_CR18","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Neil Immerman, \u201cLanguages That Capture Complexity Classes,\u201d SIAM J. Comput. 16, (1987), 760\u2013778.","journal-title":"SIAM J. Comput."},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Neil Immerman, \u201cDescriptive and Computational Complexity,\u201d Computational Complexity Theory, ed. J. Hartmanis, Proc. Symp. in Applied Math., 38, American Mathematical Society (1989), 75\u201391.","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"N. Immerman, S. Landau, \u201cThe Complexity of Iterated Multiplication,\u201d Fourth Annual Structure in Complexity Theory Symp. (1989), 104\u2013111. Revised version submitted to Information and Computation.","DOI":"10.1109\/SCT.1989.41816"},{"key":"19_CR21","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. Jones","year":"1975","unstructured":"Neil Jones, \u201cSpace-Bounded Reducibility among Combinatorial Problems,\u201d J. Computer Sys. Sci. 11 (1975), 68\u201385.","journal-title":"J. Computer Sys. Sci."},{"key":"19_CR22","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0304-3975(85)90140-9","volume":"39","author":"D. Joseph","year":"1985","unstructured":"Deborah Joseph and Paul Young, \u201cSome Remarks on Witness Functions for Non-polynomial and Non-complete sets in NP,\u201d Theoretical Computer Science 39 (1985), 225\u2013237.","journal-title":"Theoretical Computer Science"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Richard Karp, \u201cReducibility Among Combinatorial Problems,\u201d in Complexity of Computations, R.E.Miller and J.W.Thatcher, eds. (1972), Plenum Press, 85\u2013104.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Stuart Kurtz, Stephen Mahaney, James Royer, \u201cThe Structure of Complete Degrees,\u201d in Complexity Theory Retrospective (Alan Selman, Ed.), Springer-Verlag, 1990, pp. 108\u2013146.","DOI":"10.1007\/978-1-4612-4478-3_7"},{"key":"19_CR25","doi-asserted-by":"crossref","unstructured":"Stephen Lindell, \u201cA Purely Logical Characterization of Circuit Uniformity,\u201d Seventh IEEE Structure in Complexity Theory Symp. (1992), 185\u2013192.","DOI":"10.1109\/SCT.1992.215393"},{"key":"19_CR26","unstructured":"Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989."},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"Iain Stewart, \u201cUsing the Hamiltonian Operator to Capture NP,\u201d to appear in J. Comput. Sys. Sci. (1992).","DOI":"10.1016\/0022-0000(92)90043-I"},{"issue":"3\u20134","key":"19_CR28","first-page":"253","volume":"28","author":"L. G. Valiant","year":"1982","unstructured":"L.G. Valiant, \u201cReducibility By Algebraic Projections,\u201d L'Enseignement math\u00e9matique, 28, 3\u20134 (1982), 253\u201368.","journal-title":"L'Enseignement math\u00e9matique"},{"key":"19_CR29","doi-asserted-by":"crossref","unstructured":"Paul Young, \u201cJuris Hartmanis: Fundamental Contributions to Isomorphism Problems,\u201d in Complexity Theory Retrospective, Alan Selman, ed., Springer-Verlag (1990), 28\u201358.","DOI":"10.1007\/978-1-4612-4478-3_4"}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:49:15Z","timestamp":1742593755000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}