{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:29Z","timestamp":1725663689293},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569923"},{"type":"electronic","value":"9783540478904"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56992-8_25","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:00:38Z","timestamp":1330257638000},"page":"410-424","source":"Crossref","is-referenced-by-count":2,"title":["Logical characterization of bounded query classes II: Polynomial-time oracle machines"],"prefix":"10.1007","author":[{"given":"Iain A.","family":"Stewart","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"issue":"3","key":"25_CR1","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A. Borodin","year":"1989","unstructured":"A. BORODIN, S. A. COOK, P. W. DYMOND, W. L. RUZZO, AND M. TOMPA, Two applications of inductive counting for complementation problems, SIAM J. Comput., 18, 3 (1989), 559\u2013578.","journal-title":"SIAM J. Comput."},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"R. J. BEIGEL, Bounded queries to SAT and the Boolean Hierarchy, to appear, Theoret. Comput. Sci..","DOI":"10.1016\/0304-3975(91)90160-4"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"S. R. BUSS AND L. HAY, On truth-table reducibility to SAT and the Difference Hirarchy over NP, Proc. 3rd Symp. on Structure in Complexity Theory, IEEE Press (1988), 224\u2013233.","DOI":"10.1109\/SCT.1988.5282"},{"issue":"6","key":"25_CR4","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"J. CAI, T. GUNDERMANN, J. HARTMANIS, L. A. HEMACHANDRA, V. SEWELSON, K. W. WAGNER, AND G. WECHSUNG, The Boolean hierarchy I: Structural properties, SIAM J. Comput., 17, 6 (1988), 1232\u20131252.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"25_CR5","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J. Cai","year":"1989","unstructured":"J. CAI, T. GUNDERMANN, J. HARTMANIS, L. A. HEMACHANDRA, V. SEWELSON, K. W. WAGNER, AND G. WECHSUNG, The Boolean hierarchy II: Applications, SIAM J. Comput., 18, 1 (1989), 95\u2013111.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"25_CR6","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. IMMERMAN, Languages that capture complexity classes, SIAM J. Comput., 16, 4 (1987), 760\u2013778.","journal-title":"SIAM J. Comput."},{"issue":"5","key":"25_CR7","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. IMMERMAN, Nondeterministic space is closed under complementation, SIAM J. Comput., 17, 5 (1988), 935\u2013938.","journal-title":"SIAM J. Comput."},{"issue":"5","key":"25_CR8","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"J. K\u00f6bler","year":"1990","unstructured":"J. K\u00d6BLER, personal communication as cited in [Wag90].","journal-title":"SIAM J. Comput."},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1051\/ita\/1987210404191","volume":"21","author":"J. K\u00f6bler","year":"1987","unstructured":"J. K\u00d6BLER, U. SCH\u00d6NING, AND K. W. WAGNER, The difference and the truth-table hierarchies for NP, RAIRO Inform. Theory, 21 (1987), 419\u2013435.","journal-title":"RAIRO Inform. Theory"},{"issue":"3","key":"25_CR10","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1093\/logcom\/1.3.305","volume":"1","author":"I. A. Stewart","year":"1991","unstructured":"I. A. STEWART, Comparing the expressibility of languages formed using NP-complete operators, J. Logic Computat., 1, 3 (1991), 305\u2013330.","journal-title":"J. Logic Computat."},{"key":"25_CR11","unstructured":"I. A. STEWART, On completeness for NP via projection translations, Math. Systems Theory, to appear."},{"issue":"6","key":"25_CR12","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1093\/logcom\/1.6.861","volume":"1","author":"I. A. Stewart","year":"1991","unstructured":"I. A. STEWART, Complete problems involving Boolean labelled structures and projection translations, J. Logic Computat., 1, 6 (1991), 861\u2013882.","journal-title":"J. Logic Computat."},{"issue":"1","key":"25_CR13","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0022-0000(92)90043-I","volume":"45","author":"I. A. Stewart","year":"1992","unstructured":"I. A. STEWART, Using the Hamiltonian operator to capture NP, J. Comput. System Sci., 45, 1 (1992), 127\u2013151.","journal-title":"J. Comput. System Sci."},{"key":"25_CR14","first-page":"470","volume":"620","author":"I. A. Stewart","year":"1992","unstructured":"I. A. STEWART, Logical characterizations of bounded query classes I: logspace oracle machines, L.N.C.S. 620 (1992), 470\u2013479.","journal-title":"L.N.C.S."},{"issue":"5","key":"25_CR15","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. W. Wagner","year":"1990","unstructured":"K. W. WAGNER, Bounded query classes, SIAM J. Comput., 19, 5 (1990), 833\u2013846.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56992-8_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:07:55Z","timestamp":1605647275000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56992-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569923","9783540478904"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-56992-8_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}