{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:13Z","timestamp":1725488593108},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_29","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"299-310","source":"Crossref","is-referenced-by-count":3,"title":["Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions"],"prefix":"10.1007","author":[{"given":"Arfst","family":"Nickelsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Till","family":"Tantau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"29_CR1","unstructured":"A. Amir, R. Beigel, and W. Gasarch. Some connections between bounded query classes and non-uniform complexity. In Proc. 5th Structure in Complexity Theory, 1990."},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"A. Amir and W. Gasarch. Polynomial terse sets. Inf. and Computation, 77, 1988.","DOI":"10.1016\/0890-5401(88)90044-2"},{"key":"29_CR3","unstructured":"R. Beigel. Query-Limited Reducibilities. PhD thesis, Stanford University, 1987."},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"R. Beigel. Bounded queries to SAT and the boolean hierarchy. Theoretical Comput. Sci., 84(2), 1991.","DOI":"10.1016\/0304-3975(91)90160-4"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"R. Beigel, W. Gasarch, and E. Kinber. Frequency computation and bounded queries. In Proc. 10th Structure in Complexity Theory, 1995.","DOI":"10.1109\/SCT.1995.514852"},{"key":"29_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023860","volume-title":"Proc. Logical Found. of Comput. Sci.","author":"R. Beigel","year":"1992","unstructured":"R. Beigel, M. Kummer, and F. Stephan. Quantifying the amount of verboseness. In Proc. Logical Found. of Comput. Sci., volume 620 of LNCS. Springer, 1992."},{"key":"29_CR7","doi-asserted-by":"crossref","unstructured":"R. Beigel, M. Kummer, and F. Stephan. Approximable sets. In Proc. 9th Structure in Complexity Theory, 1994.","DOI":"10.1109\/SCT.1994.315822"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"R. Beigel, M. Kummer, and F. Stephan. Approximable sets. Inf. and Computation, 120(2), 1995.","DOI":"10.1006\/inco.1995.1115"},{"issue":"2","key":"29_CR9","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM J. Comput., 6(2):305\u2013322, 1977.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"29_CR10","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1006\/inco.1993.1035","volume":"104","author":"J. Goldsmith","year":"1993","unstructured":"J. Goldsmith, D. Joseph, and P. Young. Using self-reducibilities to characterize polynomial time. Inf. and Computation, 104(2):288\u2013308, 1993.","journal-title":"Inf. and Computation"},{"key":"29_CR11","volume-title":"Technical Report CS-TR-88-749","author":"J. Goldsmith","year":"1988","unstructured":"J. Goldsmith, D. A. Joseph, and P. Young. Using self-reducibilities to characterize polynomial time. Technical Report CS-TR-88-749, University of Wisconsin, Madison, 1988."},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/0304-3975(96)00094-1","volume":"155","author":"L. Hemaspaandra","year":"1996","unstructured":"L. Hemaspaandra, A. Hoene, and M. Ogihara. Reducibility classes of p-selective sets. Theoretical Comput. Sci., 155:447\u2013457, 1996.","journal-title":"Theoretical Comput. Sci."},{"key":"29_CR13","unstructured":"L. A. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe. Polynomial-time multi-selectivity. J. of Universal Comput. Sci., 3(3), 1997."},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"M. Hinrichs and G. Wechsung. Time bounded frequency computations. In Proc. 12th Conf. on Computational Complexity, 1997.","DOI":"10.1109\/CCC.1997.612314"},{"key":"29_CR15","series-title":"Lect Notes Comput Sci","volume-title":"Proc. STACS 93","author":"A. Hoene","year":"1993","unstructured":"A. Hoene and A. Nickelsen. Counting, selecting, and sorting by query-bounded machines. In Proc. STACS 93, volume 665 of LNCS. Springer, 1993."},{"key":"29_CR16","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(83)90013-2","volume":"26","author":"K.-I. Ko","year":"1983","unstructured":"K.-I. Ko. On self-reducibility and weak p-selectivity. J. Comput. Syst. Sci., 26:209\u2013221, 1983.","journal-title":"J. Comput. Syst. Sci."},{"key":"29_CR17","unstructured":"J. K\u00f6bler. On the structure of low sets. In Proc. 10th Structure in Complexity Theory, pages 246\u2013261. IEEE Computer Society Press, 1995."},{"issue":"2","key":"29_CR18","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, N. A. Lynch, and A. L. Selman. A comparison of polynomial time reducibilities. Theoretical Comput. Sci., 1(2):103\u2013123, Dec. 1975.","journal-title":"Theoretical Comput. Sci."},{"key":"29_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BFb0023468","volume-title":"Proc. STACS 97","author":"A. Nickelsen","year":"1997","unstructured":"A. Nickelsen. On polynomially \n                    \n                      \n                    \n                    $$\n\\mathcal{D}\n$$\n                  -verbose sets. In Proc. STACS 97, volume 1200 of LNCS, pages 307\u2013318. Springer, 1997."},{"key":"29_CR20","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A. Selman","year":"1979","unstructured":"A. Selman. P-selective sets, tally languages and the behaviour of polynomial time reducibilities on NP. Math. Systems Theory, 13:55\u201365, 1979.","journal-title":"Math. Systems Theory"},{"key":"29_CR21","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(82)90039-1","volume":"19","author":"A. L. Selman","year":"1982","unstructured":"A. L. Selman. Reductions on NP and p-selective sets. Theoretical Comput. Sci., 19:287\u2013304, 1982.","journal-title":"Theoretical Comput. Sci."},{"key":"29_CR22","doi-asserted-by":"publisher","first-page":"329","DOI":"10.2307\/1994272","volume":"115","author":"P. Young","year":"1965","unstructured":"P. Young. On semi-cylinders, splinters, and bounded-truth-table reducibility. Trans. of the AMS, 115:329\u2013339, 1965.","journal-title":"Trans. of the AMS"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T09:34:48Z","timestamp":1550741688000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}