{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:46:21Z","timestamp":1767339981907,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540075448"},{"type":"electronic","value":"9783540380764"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-38076-0_29","type":"book-chapter","created":{"date-parts":[[2007,6,2]],"date-time":"2007-06-02T22:30:01Z","timestamp":1180823401000},"page":"453-463","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Acceptor-Definable Counting Classes"],"prefix":"10.1007","author":[{"given":"Aggelos","family":"Kiayias","sequence":"first","affiliation":[]},{"given":"Aris","family":"Pagourtzis","sequence":"additional","affiliation":[]},{"given":"Kiron","family":"Sharma","sequence":"additional","affiliation":[]},{"given":"Stathis","family":"Zachos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,6,25]]},"reference":[{"key":"29_CR1","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: \u201cA Uniform Approach to Define Complexity Classes\u201d, Theoretical Computer Science, Vol.104, pp.263\u2013283, 1992.","journal-title":"Theoretical Computer Science"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"S. A. Fenner, L. J. Fortnow and S. A. Kurtz: \u201cGap-definable Counting Classes\u201d, Proceedings 6th Annual Structure in Complexity Theory Conference, pp.30\u201342, Chicago, IL, 1991. 453, 454","DOI":"10.1109\/SCT.1991.160241"},{"issue":"4","key":"29_CR3","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/BF01192696","volume":"29","author":"U. Hertrampf","year":"1996","unstructured":"U. Hertrampf, H. Vollmer and K. W. Wagner: \u201cOn Balanced vs. Unbalanced Computation Trees\u201d, Mathematical Systems Theory, Vol.29, No.4, pp.411\u2013421, July\/August 1996. 453","journal-title":"Mathematical Systems Theory"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"H. Hempel and G. Wechsung: \u201cThe Operators min and max on the Polynomial Hierarchy\u201d, Technical Report, TR97-025, ECCC, 1997. 454","DOI":"10.1007\/BFb0023451"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"B. Jenner, P. McKenzie and D. Th\u00e9rien: \u201cLogspace and Logtime Leaf Languages\u201d, Proceedings 9th Annual Structure in Complexity Theory Conference, pp.242\u2013254, Amsterdam, The Netherlands, 1994. 453","DOI":"10.1109\/SCT.1994.315799"},{"key":"29_CR6","unstructured":"A. Kiayias, A. Pagourtzis, K. Sharma and S. Zachos: \u201cThe Complexity of Determining the Order of Solutions\u201d, Proceedings 1st Southern Symposium on Computing, 1998, Hattiesburg, Mississippi, 1998. 453, 454, 455, 456, 457, 458, 460, 461"},{"key":"29_CR7","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: \u201cThe Complexity of Optimization Problems\u201d, Journal of Computer and System Sciences, Vol.36, No.3, pp.490\u2013509, June 1988. 454, 460","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"29_CR8","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: \u201cOn Counting and Approximation\u201d, Acta Informatica, Vol.26, No.4, pp.363\u2013379, 1989.","journal-title":"Acta Informatica"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(93)90006-I","volume":"46","author":"M. Ogiwara","year":"1993","unstructured":"M. Ogiwara and L. A. Hemachandra: \u201cA Complexity Theory for Feasible Closure Properties\u201d Journal of Computer and System Sciences, Vol.46, No.3, pp.295\u2013325, June 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"29_CR10","unstructured":"A. Pagourtzis: \u201cTrees, Paths, and Leaves in the Forest of Non-Deterministic Algorithms\u201d, PhD thesis, National Technical University of Athens, Greece, 1999. 457"},{"key":"29_CR11","unstructured":"A. Pagourtzis: \u201cOn the Complexity of Hard Counting Problems with Easy Decision Version\u201d, Proceedings 3rd Panhellenic Logic Symposium, Anogia, Crete, July 2001. 454, 458"},{"key":"29_CR12","unstructured":"A. Pagourtzis, K. Sharma and S. Zachos: \u201cComputation Trees: the Rightmost Accepting Path\u201d, Proceedings CTS Workshop on Combinatorics and Algorithms, Academia Sinica, Taipei, Taiwan, 1998. 453, 454, 461"},{"key":"29_CR13","unstructured":"C. H. Papadimitriou and S. Zachos: \u201cTwo Remarks on the Power of Counting\u201d, Theoretical Computer Science, Vol.145, 1983."},{"key":"29_CR14","unstructured":"C. H. Papadimitriou: \u201cComputational Complexity\u201d, Springer-Verlag, 1994. 462"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"S. Toda: \u201c the Computational Power of PP and \u2295P\u201d, Proceedings 30th Annual Symposium on Foundations of Computer Science (FOCS), pp.514\u2013519, Research Triangle Park, NC, 1989.","DOI":"10.1109\/SFCS.1989.63527"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"S. Toda: \u201cThe Complexity of Finding Medians\u201d, Proceedings 31st Annual Symposium on Foundations of Computer Science (FOCS), Vol.II, pp.778\u2013787, St. Louis, Missouri, October 1990. 454, 460","DOI":"10.1109\/FSCS.1990.89600"},{"issue":"1","key":"29_CR17","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"S. Toda","year":"1992","unstructured":"S. Toda and O. Watanabe: \u201cPolynomial-time 1-Turing Reductions from #PH to #P\u201d, Theoretical Computer Science, Vol.100, No.1, pp.205\u2013221, 1992. 459","journal-title":"Theoretical Computer Science"},{"key":"29_CR18","unstructured":"J. Tor\u00e1n: \u201cStructural Properties of the Counting Hierarchies\u201d, PhD thesis, Facultat d\u2019Informatica de Barcelona, 1988."},{"issue":"2","key":"29_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant: \u201cThe Complexity of Computing the Permanent\u201d, Theoretical Computer Science, Vol.8, No.2, pp.189\u2013201, April 1979. 453, 457","journal-title":"Theoretical Computer Science"},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"H. Vollmer and K. Wagner: \u201cThe Complexity of Finding Middle Elements\u201d, International Journal of Foundations of Computer Science, Vol.4, 1993.","DOI":"10.1142\/S0129054193000195"}],"container-title":["Lecture Notes in Computer Science","Advances in Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-38076-0_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T21:46:41Z","timestamp":1737064001000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-38076-0_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540075448","9783540380764"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-38076-0_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]},"assertion":[{"value":"25 June 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}