{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:17:40Z","timestamp":1725560260287},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281931"},{"type":"electronic","value":"9783540318736"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11537311_12","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T10:00:06Z","timestamp":1127815206000},"page":"125-136","source":"Crossref","is-referenced-by-count":3,"title":["On the Power of Unambiguity in Alternating Machines"],"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":"12_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":"12_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, pp. 743\u2013750. IEEE Computer Society, Los Alamitos (2002)"},{"key":"12_CR3","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":"1\u20133","key":"12_CR4","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"Blass, A., Gurevich, Y.: On the unique satisfiability problem. Information and Control\u00a055(1\u20133), 80\u201388 (1982)","journal-title":"Information and Control"},{"issue":"1","key":"12_CR5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J. Cai","year":"1989","unstructured":"Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The boolean hierarchy II: Applications. SIAM Journal on Computing\u00a018(1), 95\u2013111 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Chandra, A., Kozen, D., Stockmeyer, L.: Alternation. Journal of the ACM\u00a026(1) (1981)","DOI":"10.1145\/322234.322243"},{"key":"12_CR7","series-title":"Lecture Notes in Computer Science","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":"12_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s000370050008","volume":"7","author":"P. Crescenzi","year":"1998","unstructured":"Crescenzi, P., Silvestri, R.: Sperner\u2019s lemma and robust machines. Computational Complexity\u00a07, 163\u2013173 (1998)","journal-title":"Computational Complexity"},{"issue":"6","key":"12_CR9","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S0020-0190(99)00034-4","volume":"69","author":"L. Fortnow","year":"1999","unstructured":"Fortnow, L.: Relativized worlds with an infinite hierarchy. Information Processing Letters\u00a069(6), 309\u2013313 (1999)","journal-title":"Information Processing Letters"},{"issue":"2","key":"12_CR10","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"},{"issue":"2","key":"12_CR11","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0304-3975(90)90138-8","volume":"74","author":"J. Hartmanis","year":"1990","unstructured":"Hartmanis, J., Hemachandra, L.: Robust machines accept easy sets. Theoretical Computer Science\u00a074(2), 217\u2013225 (1990)","journal-title":"Theoretical Computer Science"},{"key":"12_CR12","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)"},{"issue":"3","key":"12_CR13","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1137\/S0097539794261970","volume":"26","author":"L. Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, L., Rothe, J.: Unambiguous computation: Boolean hierarchies and sparse Turing-complete sets. SIAM Journal on Computing\u00a026(3), 634\u2013653 (1997)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"12_CR14","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"},{"issue":"2","key":"12_CR15","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"},{"issue":"2","key":"12_CR16","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0890-5401(91)90002-J","volume":"90","author":"K. Ko","year":"1991","unstructured":"Ko, K.: Separating the low and high hierarchies by oracles. Information and Computation\u00a090(2), 156\u2013177 (1991)","journal-title":"Information and Computation"},{"key":"12_CR17","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":"12_CR18","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":"12_CR19","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":"12_CR20","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"3","key":"12_CR21","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1137\/S0097539791218640","volume":"23","author":"M. Sheu","year":"1994","unstructured":"Sheu, M., Long, T.: The extended low hierarchy is an infinite hierarchy. SIAM Journal on Computing\u00a023(3), 488\u2013509 (1994)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"12_CR22","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":"12_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.: The polynomial-time hierarchy. Theoretical Computer Science\u00a03, 1\u201322 (1976)","journal-title":"Theoretical Computer Science"},{"key":"12_CR24","unstructured":"Wagner, K.: Alternating machines using partially defined \u201cAND\u201d and \u201cOR\u201d. Technical Report 39,In: Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg (January 1992)"},{"key":"12_CR25","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","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11537311_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T02:52:40Z","timestamp":1619491960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11537311_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281931","9783540318736"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11537311_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}