{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:56:07Z","timestamp":1725468967290},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540377917"},{"type":"electronic","value":"9783540377931"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11821069_67","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T06:25:12Z","timestamp":1156487112000},"page":"777-788","source":"Crossref","is-referenced-by-count":0,"title":["Hierarchical Unambiguity"],"prefix":"10.1007","author":[{"given":"Holger","family":"Spakowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Tripathi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"67_CR1","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s00224-003-1105-7","volume":"37","author":"S. Aida","year":"2004","unstructured":"Aida, S., Cr\u00e2smaru, M., Regan, K., Watanabe, O.: Games with uniqueness properties. Theory of Computing Systems\u00a037(1), 29\u201347 (2004)","journal-title":"Theory of Computing Systems"},{"key":"67_CR2","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1109\/SFCS.2002.1181999","volume-title":"Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science","author":"V. Arvind","year":"2002","unstructured":"Arvind, V., Kurur, P.: Graph isomorphism is in SPP. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, November 2002, pp. 743\u2013750. IEEE Computer Society Press, Los Alamitos (2002)"},{"key":"67_CR3","volume-title":"Introduction to the Theory of Complexity","author":"D. Bovet","year":"1993","unstructured":"Bovet, D., Crescenzi, P.: Introduction to the Theory of Complexity. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"67_CR4","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1109\/SCT.1989.41827","volume-title":"Proceedings of the 4th Structure in Complexity Theory Conference","author":"R. Beigel","year":"1989","unstructured":"Beigel, R.: On the relativized power of additional accepting paths. In: Proceedings of the 4th Structure in Complexity Theory Conference, pp. 216\u2013224. IEEE Computer Society Press, Los Alamitos (1989)"},{"issue":"2","key":"67_CR5","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0304-3975(91)90160-4","volume":"84","author":"R. Beigel","year":"1991","unstructured":"Beigel, R.: Bounded queries to SAT and the boolean hierarchy. Theoretical Computer Science\u00a084(2), 199\u2013223 (1991)","journal-title":"Theoretical Computer Science"},{"key":"67_CR6","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1109\/SCT.1993.336538","volume-title":"Proceedings of the 8th Structure in Complexity Theory Conference","author":"R. Beigel","year":"1993","unstructured":"Beigel, R.: The polynomial method in circuit complexity. In: Proceedings of the 8th Structure in Complexity Theory Conference, San Diego, CA, USA, May 1993, pp. 82\u201395. IEEE Computer Society Press, Los Alamitos (1993)"},{"issue":"4","key":"67_CR7","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"Baker, T., Gill, J., Solovay, R.: Relativizations of the P=?NP Question. SIAM Journal on Computing\u00a04(4), 431\u2013442 (1975)","journal-title":"SIAM Journal on Computing"},{"key":"67_CR8","doi-asserted-by":"crossref","unstructured":"Blum, M., Impagliazzo, R.: Generic oracles and oracle classes. In: Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, October 1987, pp. 118\u2013126 (1987)","DOI":"10.1109\/SFCS.1987.30"},{"key":"67_CR9","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0304-3975(79)90043-4","volume":"8","author":"T. Baker","year":"1979","unstructured":"Baker, T., Selman, A.: A second step toward the polynomial hierarchy. Theoretical Computer Science\u00a08, 177\u2013187 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"67_CR10","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1006\/jcss.1997.1552","volume":"56","author":"C. Berg","year":"1998","unstructured":"Berg, C., Ulfberg, S.: A lower bound for perceptrons and an oracle separation of the PPPH hierarchy. Journal of Computer and System Sciences\u00a056(3), 263\u2013271 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"67_CR11","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1007\/978-3-540-28629-5_51","volume-title":"Mathematical Foundations of Computer Science 2004","author":"M. Cr\u00e2smaru","year":"2004","unstructured":"Cr\u00e2smaru, M., Gla\u00dfer, C., Regan, K.W., Sengupta, S.: A protocol for serializing unique strategies. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 660\u2013672. Springer, Heidelberg (2004)"},{"key":"67_CR12","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-55808-X_14","volume-title":"Mathematical Foundations of Computer Science 1992","author":"J. Cai","year":"1992","unstructured":"Cai, J., Hemachandra, L., Vysko\u010d, J.: Promise problems and access to unambiguous computation. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol.\u00a0629, pp. 162\u2013171. Springer, Heidelberg (1992)"},{"key":"67_CR13","first-page":"101","volume-title":"Complexity Theory","author":"J. Cai","year":"1993","unstructured":"Cai, J., Hemachandra, L., Vysko\u010d, J.: Promises and fault-tolerant database access. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory, pp. 101\u2013146. Cambridge University Press, Cambridge (1993)"},{"issue":"2","key":"67_CR14","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","volume":"61","author":"S. Even","year":"1984","unstructured":"Even, S., Selman, A., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Information and Control\u00a061(2), 159\u2013173 (1984)","journal-title":"Information and Control"},{"key":"67_CR15","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"Furst, M., Saxe, J., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory\u00a017, 13\u201327 (1984)","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"67_CR16","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/jcss.1996.0015","volume":"52","author":"L. Fortnow","year":"1996","unstructured":"Fortnow, L., Yamakami, T.: Generic separations. Journal of Computer and System Sciences\u00a052(1), 191\u2013197 (1996)","journal-title":"Journal of Computer and System Sciences"},{"key":"67_CR17","unstructured":"Goldreich, O.: On promise problems. Technical report TR05\u2013018, Electronic Colloquium on Computational Complexity, ECCC (2005)"},{"issue":"2","key":"67_CR18","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"Grollmann, J., Selman, A.: Complexity measures for public-key cryptosystems. SIAM Journal on Computing\u00a017(2), 309\u2013335 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"67_CR19","unstructured":"Gla\u00dfer, C., Travers, S.: Machines that can output empty words. Technical report TR05\u2013147, Electronic Colloquium on Computational Complexity, ECCC (2005)"},{"key":"67_CR20","volume-title":"Computational Limitations of Small-Depth Circuits","author":"J. H\u00e5stad","year":"1987","unstructured":"H\u00e5stad, J.: Computational Limitations of Small-Depth Circuits. MIT Press, Cambridge (1987)"},{"key":"67_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04880-1","volume-title":"The Complexity Theory Companion","author":"L. Hemaspaandra","year":"2002","unstructured":"Hemaspaandra, L., Ogihara, M.: The Complexity Theory Companion. Springer, Heidelberg (2002)"},{"issue":"1","key":"67_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(85)90085-4","volume":"37","author":"K. Ko","year":"1985","unstructured":"Ko, K.: On some natural complete operators. Theoretical Computer Science\u00a037(1), 1\u201330 (1985)","journal-title":"Theoretical Computer Science"},{"key":"67_CR23","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0304-3975(87)90078-8","volume":"52","author":"K. Ko","year":"1987","unstructured":"Ko, K.: On helping by robust oracle machines. Theoretical Computer Science\u00a052, 15\u201336 (1987)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"67_CR24","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1137\/0218027","volume":"18","author":"K. Ko","year":"1989","unstructured":"Ko, K.: Relativized polynomial time hierarchies having exactly k levels. SIAM Journal on Computing\u00a018(2), 392\u2013408 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"67_CR25","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1109\/SCT.1994.315812","volume-title":"Proceedings of the 9th Structure in Complexity Theory Conference","author":"K.-J. Lange","year":"1994","unstructured":"Lange, K.-J., Rossmanith, P.: Unambiguous polynomial hierarchies and exponential size. In: Proceedings of the 9th Structure in Complexity Theory Conference, pp. 106\u2013115. IEEE Computer Society Press, Los Alamitos (1994)"},{"issue":"1\u20132","key":"67_CR26","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0304-3975(97)00005-4","volume":"194","author":"R. Niedermeier","year":"1998","unstructured":"Niedermeier, R., Rossmanith, P.: Unambiguous computations and locally definable acceptance types. Theoretical Computer Science\u00a0194(1\u20132), 137\u2013161 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"67_CR27","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(93)90006-I","volume":"46","author":"M. Ogiwara","year":"1993","unstructured":"Ogiwara, M., Hemachandra, L.: A complexity theory for feasible closure properties. Journal of Computer and System Sciences\u00a046(3), 295\u2013325 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"67_CR28","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"67_CR29","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/978-1-4612-1872-2_11","volume-title":"Complexity Theory Retrospective\u00a0II","author":"K. Regan","year":"1997","unstructured":"Regan, K.: Polynomials and combinatorial definitions of languages. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective\u00a0II, pp. 261\u2013293. Springer, Heidelberg (1997)"},{"key":"67_CR30","first-page":"61","volume-title":"Proceedings of the 15th ACM Symposium on Theory of Computing","author":"M. Sipser","year":"1983","unstructured":"Sipser, M.: Borel sets and circuit complexity. In: Proceedings of the 15th ACM Symposium on Theory of Computing, pp. 61\u201369. ACM Press, New York (1983)"},{"issue":"5","key":"67_CR31","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF01184809","volume":"29","author":"M. Sheu","year":"1996","unstructured":"Sheu, M., Long, T.: UP and the low and high hierarchies: A relativized separation. Mathematical Systems Theory\u00a029(5), 423\u2013449 (1996)","journal-title":"Mathematical Systems Theory"},{"key":"67_CR32","unstructured":"Spakowski, H., Tripathi, R.: On the power of unambiguity in alternating machines. Theory of Computing Systems (to appear)"},{"issue":"5","key":"67_CR33","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. Wagner","year":"1990","unstructured":"Wagner, K.: Bounded query classes. SIAM Journal on Computing\u00a019(5), 833\u2013846 (1990)","journal-title":"SIAM Journal on Computing"},{"key":"67_CR34","doi-asserted-by":"crossref","unstructured":"Yao, A.: Separating the polynomial-time hierarchy by oracles. In: Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, pp. 1\u201310 (1985)","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11821069_67.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:30:47Z","timestamp":1619494247000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11821069_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540377917","9783540377931"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/11821069_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}