{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:18:21Z","timestamp":1778296701752,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1993,9,1]],"date-time":"1993-09-01T00:00:00Z","timestamp":746841600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1993,9]]},"DOI":"10.1007\/bf01371729","type":"journal-article","created":{"date-parts":[[2005,4,1]],"date-time":"2005-04-01T23:51:18Z","timestamp":1112399478000},"page":"293-310","source":"Crossref","is-referenced-by-count":36,"title":["A relationship between difference hierarchies and relativized polynomial hierarchies"],"prefix":"10.1007","volume":"26","author":[{"given":"Richard","family":"Beigel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mitsunori","family":"Ogiwara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","first-page":"31","volume-title":"Lecture Notes in Computer Science, Volume 372","author":"E. Allender","year":"1989","unstructured":"E. Allender and L. A. Hemachandra. Lower bounds for the low hierarchy. Inproceedings of the 16th ICALP, pages 31?45. Lecture Notes in Computer Science, Volume 372. Springer-Verlag, Berlin, 1989."},{"key":"CR2","first-page":"232","volume-title":"Some connections between bounded query classes and non-uniform complexity","author":"A. Amir","year":"1990","unstructured":"A. Amir, R. Beigel, and W. I. Gasarch. Some connections between bounded query classes and non-uniform complexity. InProceedings of the 5th Annual Conference on Structure in Complexity Theory, pages 232?243. IEEE Computer Society Press, New York, July 1990."},{"key":"CR3","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. I. Gasarch. Polynomial terse sets.Inform. and Comput. 77:37?56, April 1988.","journal-title":"Inform. and Comput."},{"issue":"3","key":"CR4","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1137\/0215053","volume":"15","author":"J. L. Balc\u00e1zar","year":"1986","unstructured":"J. L. Balc\u00e1zar, R. V. Book, and U. Sch\u00f6ning. Sparse sets, lowness and highness.SIAM J. Comput.,15(3):739?747, August 1986.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"CR5","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 hierarchy.Theoret. Comput. Sci.,84(2): 199?223, July 1991.","journal-title":"Theoret. Comput. Sci."},{"key":"CR6","first-page":"1","volume-title":"PP is closed under intersection","author":"R. Beigel","year":"1991","unstructured":"R. Beigel, N. Reingold, and D. Spielman. PP is closed under intersection. To appear inJ. Comput. System Sci. An earlier version appeared inProceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 1?9. ACM Press, New York, May 1991."},{"key":"CR7","first-page":"35","volume-title":"Lecture Notes in Computer Science, Volume 380","author":"A. Bertoni","year":"1989","unstructured":"A. Bertoni, D. Bruschi, D. Joseph, M. Sitharam, and P. Young. Generalized Boolean hierarchies and Boolean hierarchies over RP. InProceedings of the 7th Conference on Fundamentals of Computation Theory, pages 35?46. Lecture Notes in Computer Science, Volume 380. Springer-Verlag, Berlin, 1989."},{"key":"CR8","volume-title":"Ph.D. thesis","author":"J. Cai","year":"1986","unstructured":"J. Cai. On Some Most Probable Separations of Complexity Classes. Ph.D. thesis, Cornell University, Ithaca, NY, 1986."},{"issue":"6","key":"CR9","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): 1232?1252, December 1988.","journal-title":"SIAM J. Comput."},{"key":"CR10","series-title":"Lecture Notes in Computer Science, Volume","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/3-540-16486-3_93","volume-title":"Structure in Complexity Theory","author":"J. Cai","year":"1986","unstructured":"J. Cai and L. A. Hemachandra. The Boolean hierarchy: hardware over NP. InStructure in Complexity Theory, pages 105?124. Lecture Notes in Computer Science, Volume 223. Springer-Verlag, Berlin, June 1986."},{"key":"CR11","first-page":"169","volume-title":"The Boolean hierarchy and the polynomial hierarchy: a closer connection","author":"R. Chang","year":"1990","unstructured":"R. Chang and J. Kadin. The Boolean hierarchy and the polynomial hierarchy: a closer connection. InProceedings of the 5th Annual Conference on Structure in Complexity Theory, pages 169?178. IEEE Computer Society Press, New York, July 1990."},{"key":"CR12","series-title":"Technical Report TR","volume-title":"Department of Computer Science","author":"R. Chang","year":"1990","unstructured":"R. Chang and J. Kadin. On computing Boolean connectives of characteristic functions. Technical Report TR 90-1118, Department of Computer Science, Cornell University, Ithaca, NY, May 1990. To appear inMath. Systems Theory."},{"key":"CR13","first-page":"13","volume-title":"PP is closed under truth-table reductions","author":"L. Fortnow","year":"1991","unstructured":"L. Fortnow and N. Reingold. PP is closed under truth-table reductions. InProceedings of the 6th Annual Conference on Structure in Complexity Theory, pages 13?15. IEEE Computer Society Press, New York, June 1991."},{"key":"CR14","unstructured":"F. Green. On the power of deterministic reductions to C_P. To appear inMath. Systems Theory."},{"key":"CR15","first-page":"140","volume-title":"A survey of counting classes","author":"T. Gundermann","year":"1990","unstructured":"T. Gundermann, N. Nasser, and G. Wechsung. A survey of counting classes. InProceedings of the 5th Annual Conference on Structure in Complexity Theory, pages 140?153. IEEE Computer Society Press, New York, July 1990."},{"issue":"6","key":"CR16","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1137\/0217080","volume":"17","author":"J. Kadin","year":"1988","unstructured":"J. Kadin. The polynomial time hierarchy collapses if the Boolean hierarchy collapses.SIAM J. Comput.,17(6): 1263?1282, December 1988.","journal-title":"SIAM J. Comput."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1051\/ita\/1987210404191","volume":"21","author":"J. K\u00f6bler","year":"1987","unstructured":"J. K\u00f6bler, U. Scheming, and K. W. Wagner. The difference and truth-table hierarchies for NP.RAIRO Theoret. Inform. Appl.,21:419?435, 1987.","journal-title":"RAIRO Theoret. Inform. Appl."},{"key":"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.Theoret. Comput. Sci.,1:103?123, 1975.","journal-title":"Theoret. Comput. Sci."},{"key":"CR19","unstructured":"M. Ogiwara. On the computational power of exact counting. Unpublished manuscript, April 1990."},{"key":"CR20","volume-title":"Lecture Notes in Computer Science, Volume 211","author":"U. Sch\u00f6ming","year":"1985","unstructured":"U. Sch\u00f6ming.Complexity and Structure. Lecture Notes in Computer Science, Volume 211. Springer-Verlag, Berlin, 1985."},{"key":"CR21","unstructured":"M. Sitharam. Generalized Bounded Query Hierarchies. Ph.D. thesis, University of Wisconsin-Madison, 1990."},{"issue":"3","key":"CR22","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/116825.116858","volume":"38","author":"J. Tor\u00e1n","year":"1991","unstructured":"J. Tor\u00e1n. Complexity classes defined by counting quantifiers.J. Assoc. Comput. Mach.,38(3): 753?774, July 1991.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. W. Wagner","year":"1986","unstructured":"K. W. Wagner. The complexity of combinatorial problems with succinct input representation.Acta Inform.,23:325?356, 1986.","journal-title":"Acta Inform."},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"K. Wagner. Bounded query computations. InProceedings of the 3rd Structure in Complexity Theory Conference, pages 260?277, June 1988.","DOI":"10.1109\/SCT.1988.5286"},{"key":"CR25","unstructured":"K. W. Wagner. Number-of-query hierarchies. Technical Report 4, Institut fur Mathematik, Universitat Augsburg, 1989."},{"issue":"5","key":"CR26","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):833?846, October 1990.","journal-title":"SIAM J. Comput."},{"key":"CR27","first-page":"485","volume-title":"Lecture Notes in Computer Science, Volume 199","author":"G. Wechsung","year":"1985","unstructured":"G. Wechsung and K. Wagner. On the Boolean closure of NP. InProceedings of the 1985 International Conference on Fundamentals of Computation Theory, pages 485?493. Lecture Notes in Computer Science, Volume 199. Springer-Verlag, Berlin, 1985."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01371729.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01371729\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01371729","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T09:47:05Z","timestamp":1556876825000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01371729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,9]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,9]]}},"alternative-id":["BF01371729"],"URL":"https:\/\/doi.org\/10.1007\/bf01371729","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,9]]}}}