{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T05:16:42Z","timestamp":1736918202644,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405054"},{"type":"electronic","value":"9783540450665"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45066-1_14","type":"book-chapter","created":{"date-parts":[[2007,2,28]],"date-time":"2007-02-28T12:41:13Z","timestamp":1172666473000},"page":"181-192","source":"Crossref","is-referenced-by-count":0,"title":["On Functions and Relations"],"prefix":"10.1007","author":[{"given":"Andr\u00e9","family":"Gro\u00dfe","sequence":"first","affiliation":[]},{"given":"Harald","family":"Hempel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. EATCS Monographs in Theoretical Computer Science. Springer-Verlag, 1988. 2nd edition 1995.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"14_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/3-540-52282-4_31","volume-title":"Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science","author":"R. Beigel","year":"1990","unstructured":"R. Beigel, J. Gill, and U. Hertrampf. Counting classes: Thresholds, parity, mods, and fewness. In Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, pages 49\u201357. Springer-Verlag Lecture Notes in Computer Science #415, February 1990."},{"issue":"3","key":"14_CR3","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1137\/0213030","volume":"13","author":"R. Book","year":"1984","unstructured":"R. Book, T. Long, and A. Selman. Quantitative relativizations of complexity classes. SIAM Journal on Computing, 13(3):461\u2013487, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"14_CR4","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0022-0000(85)90053-4","volume":"30","author":"R. Book","year":"1985","unstructured":"R. Book, T. Long, and A. Selman. Qualitative relativizations of complexity classes. Journal of Computer and System Sciences, 30:395\u2013413, 1985.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"14_CR5","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"C.G.H.+.8.8._.J. Cai","year":"1988","unstructured":"CGH+88._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":"14_CR6","doi-asserted-by":"crossref","unstructured":"FGH+96._S. Fenner, F. Green, S. Homer, A. Selman, T. Thierauf, and H. Vollmer. Complements of multivalued functions. In Proceedings of the 11th Annual IEEE Conference on Computational Complexity, pages 260\u2013269. IEEE Computer Society Press, June 1996.","DOI":"10.1109\/CCC.1996.507688"},{"issue":"4","key":"14_CR7","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1137\/S0097539793247439","volume":"26","author":"S. Fenner","year":"1997","unstructured":"S. Fenner, S. Homer, M. Ogiwara, and A. Selman. Oracles that compute values. SIAM Journal on Computing, 26(4):1043\u20131065, 1997.","journal-title":"SIAM Journal on Computing"},{"key":"14_CR8","series-title":"Technical Report","volume-title":"On functions and relations","author":"A. Gro\u00dfe","year":"2003","unstructured":"A. Gro\u00dfe and H. Hempel. On functions and relations. Technical Report Math\/Inf\/01\/03, Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t Jena, Jena, Germany, January 2003."},{"key":"14_CR9","volume-title":"Functions in complexity theory","author":"H. Hempel","year":"2003","unstructured":"H. Hempel. Functions in complexity theory. Habilitation Thesis, Friedrich-Schiller-Universit\u00e4t Jena, Jena, Germany, January 2003."},{"issue":"4","key":"14_CR10","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1142\/S0129054195000214","volume":"6","author":"H.H.N.+.9.5._.L. Hemaspaandra","year":"1995","unstructured":"HHN+95._L. Hemaspaandra, A. Hoene, A. Naik, M. Ogiwara, A. Selman, T. Thierauf, and J. Wang. Nondeterministically selective sets. International Journal of Foundations of Computer Science, 6(4):403\u2013416, 1995.","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"4","key":"14_CR11","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S0097539794268315","volume":"25","author":"L. Hemaspaandra","year":"1996","unstructured":"L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman. Computing solutions uniquely collapses the polynomial hierarchy. SIAM Journal on Computing, 25(4):697\u2013708, 1996.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"14_CR12","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/203610.203611","volume":"26","author":"L. Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra and H. Vollmer. The satanic notations: Counting classes beyond # \u00b7 P and other definitional adventures. SIGACT News, 26(1):2\u201313, 1995.","journal-title":"SIGACT News"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"U. Hertrampf, H. Vollmer, and K. Wagner. On the power of number-theoretic operations with respect to counting. In Proceedings of the 10th Structure in Complexity Theory Conference, pages 299\u2013314. IEEE Computer Society Press, June 1995.","DOI":"10.1109\/SCT.1995.514868"},{"issue":"2","key":"14_CR14","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1142\/S0129054100000181","volume":"11","author":"H. Hempel","year":"2000","unstructured":"H. Hempel and G. Wechsung. The operators min and max on the polynomial hierarchy. International Journal of Foundations of Computer Science, 11(2):315\u2013342, 2000.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"14_CR15","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF00276023","volume":"26","author":"J. K\u00f6bler","year":"1989","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and J. Tor\u00e1n. On counting and approximation. Acta Informatica, 26:363\u2013379, 1989.","journal-title":"Acta Informatica"},{"key":"14_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1007\/BFb0028595","volume-title":"Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science","author":"S. Kosub","year":"1998","unstructured":"S. Kosub, H. Schmitz, and H. Vollmer. Uniformly defining complexity classes of functions. In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pages 607\u2013617. Springer-Verlag Lecture Notes in Computer Science #1373, 1998."},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"A. Meyer and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pages 125\u2013129, 1972.","DOI":"10.1109\/SWAT.1972.29"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"A. Meyer and L. Stockmeyer. Word problems requiring exponential time. In Proceedings of the 5th ACM Symposium on Theory of Computing, pages 1\u20139, 1973.","DOI":"10.1145\/800125.804029"},{"key":"14_CR19","unstructured":"C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"issue":"2","key":"14_CR20","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C. Papadimitriou","year":"1984","unstructured":"C. Papadimitriou and M. Yannakakis. The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences, 28(2):244\u2013259, 1984.","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"A. Selman. Much ado about functions. In Proceedings of the 11th Annual IEEE Conference on Computational Complexity, pages 198\u2013212. IEEE Computer Society Press, June 1996.","DOI":"10.1109\/CCC.1996.507682"},{"key":"14_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1\u201322, 1977.","journal-title":"Theoretical Computer Science"},{"key":"14_CR23","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1142\/S0129054193000195","volume":"4","author":"H. Vollmer","year":"1993","unstructured":"H. Vollmer and K. Wagner. The complexity of finding middle elements. International Journal of Foundations of Computer Science, 4:293\u2013307, 1993.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"14_CR24","unstructured":"G. Wechsung. On the boolean closure of NP. Technical Report TR N\/85\/44, Friedrich-Schiller-Universit\u00e4t Jena, December 1985."},{"key":"14_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-80024-4","volume-title":"Vorlesungen zur Komplexit\u00e4tstheorie","author":"G. Wechsung","year":"2000","unstructured":"G. Wechsung. Vorlesungen zur Komplexit\u00e4tstheorie. Teubner-Texte zur Informatik. B.G. Teubner, Stuttgart, 2000. in german."},{"issue":"1","key":"14_CR26","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"O. Watanabe","year":"1992","unstructured":"O. Watanabe and S. Toda. Polynomial time 1-Turing reductions from #PH to #P. Theoretical Computer Science, 100(1):205\u2013221, 1992.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Discrete Mathematics and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45066-1_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T09:36:59Z","timestamp":1736847419000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45066-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405054","9783540450665"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-45066-1_14","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}