{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:16Z","timestamp":1725663616079},"publisher-location":"Berlin, Heidelberg","reference-count":24,"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_22","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:14:04Z","timestamp":1330254844000},"page":"196-205","source":"Crossref","is-referenced-by-count":11,"title":["Counting, selecting, and sorting by query-bounded machines"],"prefix":"10.1007","author":[{"given":"Albrecht","family":"Hoene","sequence":"first","affiliation":[]},{"given":"Arfst","family":"Nickelsen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"A. Amir, R. Beigel, and W. Gasarch. Some connections between bounded query classes and non-uniform complexity. In Proceedings 5th Structure in Complexity Theory Conference, pages 232\u2013243. IEEE Computer Society Press, 1990.","DOI":"10.1109\/SCT.1990.113971"},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0890-5401(88)90044-2","volume":"77","author":"A. Amir","year":"1988","unstructured":"A. Amir and W. Gasarch. Polynomial terse sets. Information and Computation, 77:37\u201355, 1988.","journal-title":"Information and Computation"},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1137\/0215053","volume":"15","author":"J. Balc\u00e1zar","year":"1986","unstructured":"J. Balc\u00e1zar, R. Book, and U. Sch\u00f6ning. Sparse sets, lowness, and highness. SIAM Journal on Computing, 15:739\u2013747, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. Springer Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"R. Beigel. A structural theorem that depends quantitavely on the complexity of SAT. In Proceedings 2nd Structure in Complexity Theory Conference, pages 28\u201332. IEEE Computer Society Press, 1987.","DOI":"10.1109\/PSCT.1987.10319251"},{"key":"22_CR6","volume-title":"Technical Report 88-04","author":"R. Beigel","year":"1988","unstructured":"R. Beigel. NP-hard sets are p-superterse unless R=NP. Technical Report 88-04, Johns Hopkins University, Baltimore, MD, USA, 1988."},{"issue":"2","key":"22_CR7","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0304-3975(91)90160-4","volume":"84","author":"R. Beigel","year":"1991","unstructured":"R. Beigel. Bounded queries to SAT and the boolean hierachy. Theoretical Computer Science, 84(2):199\u2013224, 1991.","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"22_CR8","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. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy I: Structural properties. SIAM Journal on Computing, 17(6):1232\u20131252, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"R. Chang. On the structure of bounded queries to arbitrary NP sets. In Proceedings 4th Structure in Complexity Theory Conference, pages 250\u2013258. IEEE Computer Society Press, 1989.","DOI":"10.1109\/SCT.1989.41832"},{"key":"22_CR10","doi-asserted-by":"crossref","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"R. P. Dilworth","year":"1950","unstructured":"R. P. Dilworth. A decomposition theorem for partially ordered sets. Ann. of Math., 51:161\u2013166, 1950.","journal-title":"Ann. of Math."},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"W. Gasarch. Bounded queries in recursion theory: A survey. In Proceedings 6th Structure in Complexity Theory Conference, pages 62\u201378. IEEE Computer Society Press, 1991.","DOI":"10.1109\/SCT.1991.160245"},{"key":"22_CR12","unstructured":"W. Gasarch, L. Hemachandra, and A. Hoene. On checking versus evaluating multiple queries. Information and Computation. To appear."},{"issue":"3","key":"22_CR13","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L. Hemachandra","year":"1989","unstructured":"L. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39(3):299\u2013322, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR14","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 Journal on Computing, 17:935\u2013938, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR15","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/0022-0000(89)90024-X","volume":"39","author":"J. Kadin","year":"1989","unstructured":"J. Kadin. PNP[log n] and sparse Turing complete sets for NP. Journal of Computer and System Sciences, 39:282\u2013298, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR16","unstructured":"D. Knuth. The Art of Computer Programming III. Addison Wesley, second edition, 1973."},{"key":"22_CR17","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. Krentel","year":"1988","unstructured":"M. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36:490\u2013509, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR18","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. Mahaney","year":"1982","unstructured":"S. Mahaney. Sparse complete sets for NP: solution to a conjecture of Berman and Hartmanis. Journal of Computer and System Sciences, 25:130\u2013143, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings 6th GI Conference on Theoretical Computer Science, pages 269\u2013276. Springer-Verlag Lecture Notes in Computer Science #145, 1983.","DOI":"10.1007\/BFb0036487"},{"key":"22_CR20","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"U. Sch\u00f6ning. A low and a high hierarchy in NP. Journal of Computer and system sciences, 27:14\u201328, 1983.","journal-title":"Journal of Computer and system sciences"},{"key":"22_CR21","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1016\/0022-0000(81)90068-4","volume":"23","author":"A. Selman","year":"1981","unstructured":"A. Selman. Some observations on NP real numbers and P-selective sets. Journal of Computer and System Sciences, 23:326\u2013332, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR22","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/S0019-9958(82)80084-3","volume":"1","author":"A. Selman","year":"1982","unstructured":"A. Selman. Analogues of semirecursive sets and effective reducibilities to the study of NP complexity. Information and Control, 1:36\u201351, 1982.","journal-title":"Information and Control"},{"key":"22_CR23","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279\u2013284, 1988.","journal-title":"Acta Informatica"},{"issue":"5","key":"22_CR24","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. Wagner","year":"1990","unstructured":"K. Wagner. Bounded query classes. SIAM Journal on Computing, 19(5):833\u2013846, 1990.","journal-title":"SIAM Journal on Computing"}],"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_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T14:50:22Z","timestamp":1713624622000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}