{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T20:40:13Z","timestamp":1736109613087,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540642305"},{"type":"electronic","value":"9783540697053"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0028595","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:33:39Z","timestamp":1132644819000},"page":"607-617","source":"Crossref","is-referenced-by-count":3,"title":["Uniformly defining complexity classes of functions"],"prefix":"10.1007","author":[{"given":"Sven","family":"Kosub","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heinz","family":"Schmitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"53_CR1","series-title":"Texts in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-79235-9","volume-title":"Structural Complexity I","author":"J. L. Balc\u00e1zar","year":"1995","unstructured":"J. L. Balc\u00e1zar, J. Diaz, and J. Gabarr\u00f3. Structural Complexity I. Texts in Theoretical Computer Science. Springer-Verlag, Berlin Heidelberg, 2nd edition, 1995.","edition":"2nd edition"},{"key":"53_CR2","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1137\/0213030","volume":"13","author":"R. V. Book","year":"1984","unstructured":"R. V. Book, T. Long, and A. Selman. Quantitative relativizations of complexity classes. SIAM Journal on Computing, 13:461\u2013487, 1984.","journal-title":"SIAM Journal on Computing"},{"unstructured":"B. Borchert. Predicate classes, promise classes, and the acceptance power of regular languages. PhD thesis, Naturwissenschaftlich-Mathematische Fakult\u00e4t, Universit\u00e4t Heidelberg, 1994.","key":"53_CR3"},{"key":"53_CR4","series-title":"International Series in Computer Science","volume-title":"Introduction to the Theory of Complexity","author":"D. P. Bovet","year":"1994","unstructured":"D. P. Bovet and P. Crescenzi. Introduction to the Theory of Complexity. International Series in Computer Science. Prentice Hall, London, 1994."},{"key":"53_CR5","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(92)90125-Y","volume":"104","author":"D. P. Bovet","year":"1992","unstructured":"D. P. Bovet, P. Crescenzi, and R. Silvestri. A uniform approach to define complexity classes. Theoretical Computer Science, 104:263\u2013283, 1992.","journal-title":"Theoretical Computer Science"},{"key":"53_CR6","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. Fenner","year":"1994","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48:116\u2013148, 1994.","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"C. Gla\u00dfer and G. Wechsung. Relativizing function classes. Manuscript, 1997.","key":"53_CR7"},{"issue":"1","key":"53_CR8","first-page":"2","volume":"26","author":"L. Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra and H. Vollmer. The satanic notations: counting classes beyond #P and other definitional adventures. Complexity Theory Column 8, ACM SIGACT-Newsletter, 26(1):2\u201313, 1995.","journal-title":"Complexity Theory Column 8, ACM SIGACT-Newsletter"},{"doi-asserted-by":"crossref","unstructured":"H. Hempel and G. Wechsung. The operators min and max on the polynomial hierarchy. In Proceedings 14th Symposium on Theoretical Aspects of Computer Science, volume 1200 of Lecture Notes in Computer Science, pages 93\u2013104. Springer-Verlag, 1997.","key":"53_CR9","DOI":"10.1007\/BFb0023451"},{"doi-asserted-by":"crossref","unstructured":"U. Hertrampf. Classes of bounded counting type and their inclusion relations. In Proceedings 12th Symposium on Theoretical Aspects of Computer Science, volume 900 of Lecture Notes in Computer Science, pages 60\u201370. Springer-Verlag, 1995.","key":"53_CR10","DOI":"10.1007\/3-540-59042-0_62"},{"doi-asserted-by":"crossref","unstructured":"U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, and K. W. Wagner. On the power of polynomial time bit-reductions. In Proceedings 8th Structure in Complexity Theory, pages 200\u2013207, 1993.","key":"53_CR11","DOI":"10.1109\/SCT.1993.336526"},{"doi-asserted-by":"crossref","unstructured":"U. Hertrampf, H. Vollmer, and K. W. Wagner. On the power of number-theoretic operations with respect to counting. In Proceedings 10th Structure in Complexity Theory, pages 299\u2013314, 1995.","key":"53_CR12","DOI":"10.1109\/SCT.1995.514868"},{"doi-asserted-by":"crossref","unstructured":"B. Jenner, P. McKenzie, and D. Th6rien. Logspate and logtime leaf languages. In 9th Annual Conference Structure in Complexity Theory, pages 242\u2013254, 1994.","key":"53_CR13","DOI":"10.1109\/SCT.1994.315799"},{"key":"53_CR14","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0304-3975(94)00080-3","volume":"141","author":"B. Jenner","year":"1995","unstructured":"B. Jenner and J. Tor\u00e1n. Computing functions with parallel queries to NP. Theoretical Computer Science, 141:175\u2013193, 1995.","journal-title":"Theoretical Computer Science"},{"unstructured":"J. K\u00f6bler. Strukturelle Komplexitdt von Anzahlproblemen. PhD thesis, Universit\u00e4t Stuttgart, Fakult\u00e4t f\u00fcr Informatik, 1989.","key":"53_CR15"},{"key":"53_CR16","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"},{"unstructured":"S. Kosub. On cluster machines and function classes. Technical Report 172, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, 1997.","key":"53_CR17"},{"key":"53_CR18","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. W. Krentel","year":"1988","unstructured":"M. W. Krentel. The complexity of optimization functions. Journal of Computer and System Sciences, 36:490\u2013509, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"53_CR19","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(92)90073-O","volume":"97","author":"M. W. Krentel","year":"1992","unstructured":"M. W. Krentel. Generalizations of OptP to the polynomial hierarchy. Theoretical Computer Science, 97:183\u2013198, 1992.","journal-title":"Theoretical Computer Science"},{"key":"53_CR20","volume-title":"Computational Complexity","author":"C. H. Papadimitriou","year":"1994","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison-Wesley, Reading, MA, 1994."},{"unstructured":"H. Schmitz. Nichtdeterministische Polynomialzeit-Berechnung von Funktionen. Master's thesis, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, 1996.","key":"53_CR21"},{"key":"53_CR22","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/S0022-0000(05)80009-1","volume":"48","author":"A. Selman","year":"1994","unstructured":"A. Selman. A taxonomy on complexity classes of functions. Journal of Computer and System Sciences, 48:357\u2013381, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"53_CR23","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda. PP is as hard as the polynomial time hierarchy. SIAM Journal on Computing, 20:865\u2013877, 1991.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"53_CR24","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0208032","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of enumeration and reliabilty problems. SIAM Journal of Computing, 8(3):411\u2013421, 1979.","journal-title":"SIAM Journal of Computing"},{"key":"53_CR25","first-page":"51","volume":"57","author":"N. K. Vereshchagin","year":"1993","unstructured":"N. K. Vereshchagin. Relativizable and non-relativizable theorems in the polynomial theory of algorithms. Izvestija Rossijskoj Akademii Nauk, 57:51\u201390, 1993. In Russian.","journal-title":"Izvestija Rossijskoj Akademii Nauk"},{"doi-asserted-by":"crossref","unstructured":"H. Vollmer. On different reducibility notions for function classes. In Proceedings 11th Symposium on Theoretical Aspects of Computer Science, volume 775 of Lecture Notes in Computer Science, pages 449\u2013460. Springer-Verlag, 1994.","key":"53_CR26","DOI":"10.1007\/3-540-57785-8_162"},{"key":"53_CR27","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1142\/S0129054193000195","volume":"4","author":"H. Vollmer","year":"1993","unstructured":"H. Vollmer and K. W. 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":"53_CR28","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1006\/inco.1995.1109","volume":"120","author":"H. Vollmer","year":"1995","unstructured":"H. Vollmer and K. W. Wagner. Complexity classes of optimization functions. Information and Computation, 120:198\u2013219, 1995.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","STACS 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028595","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T20:06:30Z","timestamp":1736107590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028595"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540642305","9783540697053"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/bfb0028595","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}