{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:50:46Z","timestamp":1725663046151},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167617"},{"type":"electronic","value":"9783540398592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16761-7_70","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:50:55Z","timestamp":1330177855000},"page":"206-214","source":"Crossref","is-referenced-by-count":3,"title":["Decompositions of nondeterministic reductions"],"prefix":"10.1007","author":[{"given":"Klaus-J\u00f6rn","family":"Lange","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, L. Stockmeyer: Alternation, J. Assoc. Comput. Mach. 28 (1981), 114\u2013133.","journal-title":"J. Assoc. Comput. Mach."},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"S. Cook: The complexity of theorem proving procedures, Proc. of the 3rd Annual Symp. on Theory of Computing, 1971, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"22_CR3","unstructured":"P. Flajolet, J. Steyaert: Complexity of classes of languages and operators, IRIA Laboria, Rap. de Recherche No. 92, Nov. 1974."},{"key":"22_CR4","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. Ladner","year":"1976","unstructured":"R. Ladner, N. Lynch: Relativization of questions about log space computability, Math. Systems Theory 10 (1976), 19\u201332.","journal-title":"Math. Systems Theory"},{"key":"22_CR5","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, N. Lynch, A. Selman: A comparison of polynomial time reducibilities, Theoret. Comput. Sci. 1 (1975), 103\u2013123.","journal-title":"Theoret. Comput. Sci."},{"key":"22_CR6","unstructured":"K.-J. Lange: Nondeterministic log-space reductions, Proc. of the 11th Symp. of Math. Foundations of Comput. Science, 1984, Springer LNCS 176, 378\u2013388."},{"key":"22_CR7","unstructured":"K.-J. Lange: Nichtdeterministische Reduktionen und Logarithmische Hierarchien, submitted as \u2018Habilitationsschrift\u2019 at the University of Hamburg, 1985, in German."},{"key":"22_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(82)90085-8","volume":"21","author":"T. Long","year":"1982","unstructured":"T. Long: Strong nondeterministic polynomial-time reducibilities, Theoret. Comput. Sci. 21 (1982), 1\u201325.","journal-title":"Theoret. Comput. Sci."},{"key":"22_CR9","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1145\/322033.322037","volume":"24","author":"N. Lynch","year":"1977","unstructured":"N. Lynch: Log space recognition and translation of parenthesis languages, J. Assoc. Comput. Mach. 24 (1977), 583\u2013590.","journal-title":"J. Assoc. Comput. Mach."},{"key":"22_CR10","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C. Papadimitriou","year":"1984","unstructured":"C. Papadimitriou, M. Yannakakis: The complexity of facets (and some facets of complexity), J. Comput. System Sci. 28 (1984), 244\u2013259.","journal-title":"J. Comput. System Sci."},{"key":"22_CR11","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W. Ruzzo","year":"1980","unstructured":"W. Ruzzo: Tree-size bounded alternation, J. Comput. System Sci. 21 (1980), 218\u2013235.","journal-title":"J. Comput. System Sci."},{"key":"22_CR12","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"W. Ruzzo: On uniform circuit complexity, J. Comput. System Sci. 22 (1981), 365\u2013383.","journal-title":"J. Comput. System Sci."},{"key":"22_CR13","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","volume":"28","author":"W. Ruzzo","year":"1984","unstructured":"W. Ruzzo, J. Simon, M. Tompa: Space-bounded hierarchies and probabilistic computations, J. Comput. System Sci. 28 (1984), 216\u2013230.","journal-title":"J. Comput. System Sci."},{"key":"22_CR14","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF01744581","volume":"16","author":"W. Savitch","year":"1983","unstructured":"W. Savitch: A note on relativized log space, Math. Systems Theory 16 (1983), 229\u2013235.","journal-title":"Math. Systems Theory"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer, A. Meyer: Word problems requiring exponential time: preliminary report, Proc. of the 5th Annual ACM Symp. on Theory of Computing, 1973, 1\u20139.","DOI":"10.1145\/800125.804029"},{"key":"22_CR16","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"C. Wrathall: Complete sets and the polynomial-time hierarchy, Theoret. Comput. Sci. 3 (1976), 23\u201333.","journal-title":"Theoret. Comput. Sci."},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"B. Kirsig, K.-J. Lange: Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE (log n) \u2260 NSPACE (log n), 1986, submitted for publication.","DOI":"10.1016\/0020-0190(87)90087-1"}],"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-16761-7_70.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:10:53Z","timestamp":1605625853000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16761-7_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167617","9783540398592"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-16761-7_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}