{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:03Z","timestamp":1760202603521},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642020162"},{"type":"electronic","value":"9783642020179"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02017-9_17","type":"book-chapter","created":{"date-parts":[[2009,5,11]],"date-time":"2009-05-11T15:38:06Z","timestamp":1242056286000},"page":"138-149","source":"Crossref","is-referenced-by-count":7,"title":["A Computational Proof of Complexity of Some Restricted Counting Problems"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingji","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"17_CR1","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.ic.2006.09.005","volume":"205","author":"A.A. Bulatov","year":"2007","unstructured":"Bulatov, A.A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. Inf. Comput.\u00a0205(5), 651\u2013678 (2007)","journal-title":"Inf. Comput."},{"issue":"2-3","key":"17_CR2","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"A.A. Bulatov","year":"2005","unstructured":"Bulatov, A.A., Grohe, M.: The complexity of partition functions. Theor. Comput. Sci.\u00a0348(2-3), 148\u2013186 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P.: Holographic Algorithms: From Art to Science. In: Proceedings of STOC 2007, pp. 401\u2013410 (2007)","DOI":"10.1145\/1250790.1250850"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. In: FOCS 2008, pp. 644\u2013653 (2008)","DOI":"10.1109\/FOCS.2008.34"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holant Problems and Counting CSP. In: STOC 2009 (to appear, 2009)","DOI":"10.1145\/1536414.1536511"},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/3-540-07407-4_17","volume-title":"Automata Theory and Formal Languages","author":"G. Collins","year":"1975","unstructured":"Collins, G.: Quantifier Elimination for Real Closed Fields by Cylindric Algebraic Decomposition. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol.\u00a033, pp. 134\u2013183. Springer, Heidelberg (1975)"},{"issue":"1","key":"17_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of Generalized Satisfiability Counting Problems. Inf. Comput.\u00a0125(1), 1\u201312 (1996)","journal-title":"Inf. Comput."},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity classifications of boolean constraint satisfaction problems. SIAM Monographs on Discrete Mathematics and Applications (2001)","DOI":"10.1137\/1.9780898718546"},{"key":"17_CR9","unstructured":"Dyer, M.E., Goldberg, L.A., Jerrum, M.: The Complexity of Weighted Boolean #CSP CoRR abs\/0704.3683 (2007)"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Dyer, M.E., Goldberg, L.A., Paterson, M.: On counting homomorphisms to directed acyclic graphs. J. ACM\u00a054(6) (2007)","DOI":"10.1145\/1314690.1314691"},{"issue":"3-4","key":"17_CR11","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"M.E. Dyer","year":"2000","unstructured":"Dyer, M.E., Greenhill, C.S.: The complexity of counting graph homomorphisms. Random Struct. Algorithms\u00a017(3-4), 260\u2013289 (2000)","journal-title":"Random Struct. Algorithms"},{"key":"17_CR12","unstructured":"Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. CoRR abs\/0804.1932 (2008)"},{"key":"17_CR13","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. J. Combin. Theory Ser. B\u00a048, 92\u2013110 (1990)","journal-title":"J. Combin. Theory Ser. B"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Tarski, A.: A Decision Method for Elementary Algebra and Geometry, Univ. of Calif. (1951)","DOI":"10.1525\/9780520348097"},{"issue":"2","key":"17_CR15","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"S.P. Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The Complexity of Counting in Sparse, Regular, and Planar Graphs. SIAM J. Comput.\u00a031(2), 398\u2013427 (2001)","journal-title":"SIAM J. Comput."},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Holographic Algorithms (Extended Abstract). In: Proc. 45th IEEE Symposium on Foundations of Computer Science, pp. 306\u2013315 (2004)","DOI":"10.1109\/FOCS.2004.34"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02017-9_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T05:21:55Z","timestamp":1633411315000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02017-9_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642020162","9783642020179"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02017-9_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}