{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:50:53Z","timestamp":1725573053740},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540278290"},{"type":"electronic","value":"9783540315803"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11527695_3","type":"book-chapter","created":{"date-parts":[[2010,12,20]],"date-time":"2010-12-20T17:06:47Z","timestamp":1292864807000},"page":"30-45","source":"Crossref","is-referenced-by-count":6,"title":["An Algebraic Approach to the Complexity of Generalized Conjunctive Queries"],"prefix":"10.1007","author":[{"given":"Michael","family":"Bauland","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philippe","family":"Chapdelaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"Creignou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miki","family":"Hermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","volume-title":"Foundation of databases","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundation of databases. Addison-Wesley, Reading (1995)"},{"issue":"4","key":"3_CR2","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/954092.954101","volume":"34","author":"E. B\u00f6hler","year":"2003","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part\u00a0I: Post\u2019s lattice with applications to complexity theory. SIGACT News, Complexity Theory Column\u00a042,\u00a034(4), 38\u201352 (2003)","journal-title":"SIGACT News, Complexity Theory Column\u00a042,"},{"issue":"1","key":"3_CR3","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/970831.970840","volume":"35","author":"E. B\u00f6hler","year":"2004","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part\u00a0II: Constraint satisfaction problems. SIGACT News, Complexity Theory Column\u00a043,\u00a035(1), 22\u201335 (2004)","journal-title":"SIGACT News, Complexity Theory Column\u00a043,"},{"key":"3_CR4","unstructured":"Creignou, N., Hermann, M.: On #P-completeness of some counting problems. Research report 2144, Institut de Recherche en Informatique et en Automatique (December 1993), http:\/\/www.lix.polytechnique.fr\/~hermann\/publications\/satcount.ps.gz"},{"issue":"1","key":"3_CR5","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. Information and Computation\u00a0125(1), 1\u201312 (1996)","journal-title":"Information and Computation"},{"key":"3_CR6","volume-title":"SIAM Monographs on Discrete Mathematics and Applications","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. In: SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a07, SIAM, Philadelphia (2001)"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Durand, A., Hermann, M., Kolaitis, P.G.: Subtractive reductions and complete problems for counting complexity classes. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol.\u00a01893, pp. 323\u2013332. Springer, Heidelberg (2000): (To appear in Theoretical Computer Science)","DOI":"10.1007\/3-540-44612-5_28"},{"issue":"1","key":"3_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/203610.203611","volume":"26","author":"L.A. Hemaspaandra","year":"1995","unstructured":"Hemaspaandra, L.A., Vollmer, H.: The satanic notations: Counting classes beyond #P and other definitional adventures. SIGACT News, Complexity Theory Column\u00a08\u00a026(1), 2\u201313 (1995)","journal-title":"SIGACT News, Complexity Theory Column\u00a08"},{"issue":"4","key":"3_CR9","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. Journal of the Association for Computing Machinery\u00a044(4), 527\u2013548 (1997)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"3_CR10","unstructured":"Jonsson, P., Krokhin, A.: Computational complexity of auditing finite attributes in statistical databases. In: Proceedings Structural Theory of Automata, Semigroups and Universal Algebra, Montreal, Canada (July 2003)"},{"issue":"1","key":"3_CR11","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/S0022-0000(02)00036-3","volume":"66","author":"J. Kleinberg","year":"2003","unstructured":"Kleinberg, J., Papadimitriou, C., Raghavan, P.: Auditing Boolean attributes. Journal of Computer and System Science\u00a066(1), 244\u2013253 (2003)","journal-title":"Journal of Computer and System Science"},{"issue":"4","key":"3_CR12","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF00276023","volume":"26","author":"J. K\u00f6bler","year":"1989","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: On counting and approximation. Acta Informatica\u00a026(4), 363\u2013379 (1989)","journal-title":"Acta Informatica"},{"issue":"2","key":"3_CR13","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P.G. Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Science\u00a061(2), 302\u2013332 (2000)","journal-title":"Journal of Computer and System Science"},{"key":"3_CR14","unstructured":"Krokhin, A., Jonsson, P.: Recognizing frozen variables in constraint satisfaction problems. Technical Report TR03-062, Electronic Colloquium on Computational Complexity (2003)"},{"key":"3_CR15","first-page":"233","volume-title":"Proceeding 21st Symposium on Principles of Database Systems (PODS 2002)","author":"M. Lenzerini","year":"2002","unstructured":"Lenzerini, M.: Data integration: a theoretical perspective. In: Proceeding 21st Symposium on Principles of Database Systems (PODS 2002). SIGACT-SIGMOD-SIGART, Madison (Wisconsin, USA), pp. 233\u2013246. ACM Press, New York (2002)"},{"key":"3_CR16","volume-title":"Theories of Computability","author":"N. Pippenger","year":"1997","unstructured":"Pippenger, N.: Theories of Computability. Cambridge University Press, Cambridge (1997)"},{"key":"3_CR17","unstructured":"P\u00f6schel, R.: Galois connection for operations and relations. Technical Report MATH-AL-8-2001, Technische Universit\u00e4t Dresden (2001)"},{"key":"3_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-5547-1","volume-title":"Funktionen- und Relationenalgebren","author":"R. P\u00f6schel","year":"1979","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.A.: Funktionen- und Relationenalgebren. Deutscher Verlag der Wissenschaften, Berlin (1979)"},{"key":"3_CR19","first-page":"1","volume":"5","author":"E.L. Post","year":"1941","unstructured":"Post, E.L.: The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies\u00a05, 1\u2013122 (1941)","journal-title":"Annals of Mathematical Studies"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings 10th Symposium on Theory of Computing (STOC 1978), San Diego (California, USA), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"issue":"2-3","key":"3_CR21","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1023\/A:1009891813863","volume":"4","author":"C. Silberstein","year":"2000","unstructured":"Silberstein, C., Brin, S., Motwani, R., Ullman, J.D.: Scalable techniques for mining causal structures. Data Mining and Knowledge Discovery\u00a04(2-3), 163\u2013192 (2000)","journal-title":"Data Mining and Knowledge Discovery"},{"key":"3_CR22","unstructured":"Toda, S.: Computational complexity of counting complexity classes. PhD thesis, Tokyo Institute of Technology, Department of Computer Science, Tokyo, Japan (1991)"},{"issue":"1","key":"3_CR23","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"S. Toda","year":"1992","unstructured":"Toda, S., Watanabe, O.: Polynomial-time 1-Turing reductions from #PH to #P. Theoretical Computer Science\u00a0100(1), 205\u2013221 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"3_CR24","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"3_CR25","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM Journal on Computing\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Widom, J.: Research problems in data warehousing. In: Proceedings 4th International Conference on Information and Knowledge Management (CIKM 1995), Baltimore (Maryland, USA), pp. 25\u201330. Association for Computing Machinery (1995)","DOI":"10.1145\/221270.221319"},{"issue":"1","key":"3_CR27","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"Wrathall, C.: Complete sets and the polynomial-time hierarchy. Theoretical Computer Science\u00a03(1), 23\u201333 (1976)","journal-title":"Theoretical Computer Science"},{"key":"3_CR28","first-page":"316","volume-title":"Proceedings SIGMOD International Conference on Management of Data","author":"Y. Zhuge","year":"1995","unstructured":"Zhuge, Y., Garcia-Molina, H., Hammer, J., Widom, J.: View maintenance in a warehousing environment. In: Carey, M.J., Schneider, D.A. (eds.) Proceedings SIGMOD International Conference on Management of Data, San Jose (California, USA), pp. 316\u2013327. ACM Press, New York (1995)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11527695_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,2]],"date-time":"2024-04-02T05:06:25Z","timestamp":1712034385000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11527695_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540278290","9783540315803"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/11527695_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}