{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:58:38Z","timestamp":1725663518432},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540510833"},{"type":"electronic","value":"9783540461524"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51083-4_77","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:41:16Z","timestamp":1330184476000},"page":"415-426","source":"Crossref","is-referenced-by-count":3,"title":["Succinct representations of counting problems"],"prefix":"10.1007","author":[{"given":"Jacobo","family":"Tor\u00e1n","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"35_CR1","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0304-3975(76)90057-8","volume":"1","author":"R.V. Book","year":"1976","unstructured":"R.V. Book: Translational lemmas, polynomial time, and (log n)\n                  j\n                 space. Theoret. Comput. Sci. 1 (1976), 215\u2013226.","journal-title":"Theoret. Comput. Sci."},{"key":"35_CR2","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"A.K. Chandra, D.C. Kozen, L.J. Stockmeyer: Alternation. Journal ACM 28 (1981), 114\u2013133.","journal-title":"Journal ACM"},{"key":"35_CR3","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/0022-0000(86)90036-X","volume":"32","author":"B.S. Chlebus","year":"1986","unstructured":"B.S. Chlebus: Domino-Tiling games. Journal Comput. Syst. Sci. 32 (1986), 374\u2013392.","journal-title":"Journal Comput. Syst. Sci."},{"key":"35_CR4","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"H. Galperin, A. Wigderson: succinct representations of graphs. Information and Control 56 (1983), 183\u2013198.","journal-title":"Information and Control"},{"key":"35_CR5","unstructured":"E. Gr\u00e4del: Domino Games and complexity. Manuscript Universit\u00e0 di Pisa (1988)."},{"key":"35_CR6","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1145\/321724.321727","volume":"19","author":"O. Ibarra","year":"1972","unstructured":"O. Ibarra: A note concerning nondeterministic tape complexities. Journal ACM 19 (1972), 608\u2013612.","journal-title":"Journal ACM"},{"key":"35_CR7","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"C.H. Papadimitriou","year":"1986","unstructured":"C.H. Papadimitriou, M. Yannakakis: A note on succinct representations of graphs. Information and Control 71 (1986), 181\u2013185.","journal-title":"Information and Control"},{"key":"35_CR8","unstructured":"J. Simon: On some central problems in computational complexity. Ph.D. Thesis, Cornell University (1975)."},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"M. Sipser: Borel sets and circuit complexity. Proc. 15th STOC (1983), 61\u201369.","DOI":"10.1145\/800061.808733"},{"key":"35_CR10","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1145\/3149.3158","volume":"32","author":"S. Skium","year":"1985","unstructured":"S. Skium, L.G. Valiant: A complexity theory based on boolean algebra. Journal ACM 32 (1985), 484\u2013502.","journal-title":"Journal ACM"},{"key":"35_CR11","unstructured":"J. Tor\u00e1n: Structural properties of the counting hierarchies. Ph. D. Thesis. Facultat d'Inform\u00e0tica de Barcelona. (1988)."},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"J. Tor\u00e1n: An oracle characterization of the counting hierarchy. Proceedings 3rd Structure in Complexity Theory Conference (1988), 213\u2013224.","DOI":"10.1109\/SCT.1988.5281"},{"key":"35_CR13","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. Wagner","year":"1986","unstructured":"K. Wagner: The complexity of combinatorial problems with succinct input representation. Acta Informatica 23 (1986), 325\u2013356.","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","Applied Algebra, Algebraic Algorithms and Error-Correcting Codes"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51083-4_77.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:00:52Z","timestamp":1619557252000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51083-4_77"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540510833","9783540461524"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-51083-4_77","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}