{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:55:13Z","timestamp":1758272113601},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153952"},{"type":"electronic","value":"9783642153969"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15396-9_4","type":"book-chapter","created":{"date-parts":[[2010,9,6]],"date-time":"2010-09-06T07:00:16Z","timestamp":1283756416000},"page":"9-23","source":"Crossref","is-referenced-by-count":11,"title":["Testing Expressibility Is Hard"],"prefix":"10.1007","author":[{"given":"Ross","family":"Willard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF01070906","volume":"5","author":"V.G. Bodnar\u010duk","year":"1969","unstructured":"Bodnar\u010duk, V.G., Kalu\u017enin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for Post algebras. I. Cybernetics and Systems Analysis\u00a05, 243\u2013252 (1969)","journal-title":"I. Cybernetics and Systems Analysis"},{"key":"4_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59207-2","volume-title":"The Classical Decision Problem","author":"E. B\u00f6rger","year":"1997","unstructured":"B\u00f6rger, E., Gr\u00e4del, E., Gurevich, Y.: The Classical Decision Problem. Springer, Heidelberg (1997)"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput.\u00a034, 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"4_CR4","unstructured":"ten Cate, B.: Notes on AIM CSP workshop, April 21 (2008), \n                    \n                      http:\/\/www.aimath.org\/WWN\/constraintsatis\/constraintsatis.pdf"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/B978-155860890-0\/50012-8","volume-title":"Constraint Processing","author":"D. Cohen","year":"2003","unstructured":"Cohen, D., Jeavons, P.: Tractable constraint languages. In: Dechter, R. (ed.) Constraint Processing, pp. 299\u2013331. Elsevier, San Francisco (2003)"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"1103","DOI":"10.1016\/j.jcss.2008.02.005","volume":"74","author":"N. Creignou","year":"2008","unstructured":"Creignou, N., Kolaitis, P., Zanuttini, B.: Structure identification of boolean relations and plain bases for co-clones. J. Comput. System Sci.\u00a074, 1103\u20131115 (2008)","journal-title":"J. Comput. System Sci."},{"key":"4_CR7","unstructured":"Dalmau, V.: Computational complexity of problems over generalized formulas. PhD thesis, Universitat Polit\u00e9cnica de Catalunya (2000)"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0004-3702(92)90009-M","volume":"58","author":"R. Dechter","year":"1992","unstructured":"Dechter, R., Pearl, J.: Structure identification in relational data. Artificial Intelligence\u00a058, 237\u2013270 (1992)","journal-title":"Artificial Intelligence"},{"key":"4_CR9","doi-asserted-by":"crossref","first-page":"95","DOI":"10.2140\/pjm.1968.27.95","volume":"27","author":"D. Geiger","year":"1968","unstructured":"Geiger, D.: Closed systems of functions and predicates. Pacific J. Math.\u00a027, 95\u2013100 (1968)","journal-title":"Pacific J. Math."},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(89)90023-7","volume":"43","author":"E. Gr\u00e4del","year":"1989","unstructured":"Gr\u00e4del, E.: Dominoes and the complexity of subclasses of logical theories. Ann. Pure Appl. Logic\u00a043, 1\u201330 (1989)","journal-title":"Ann. Pure Appl. Logic"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/3-540-49481-2_2","volume-title":"Principles and Practice of Constraint Programming - CP98","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P.: Constructing Constraints. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol.\u00a01520, pp. 2\u201316. Springer, Heidelberg (1998)"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P.: On the algebraic structure of combinatorial problems. Theoret. Comput. Sci.\u00a0200, 185\u2013204 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR13","series-title":"LNAI","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-02716-1_1","volume-title":"Automated Reasoning with Analytic Tableaux and Related Methods","author":"P. Jeavons","year":"2009","unstructured":"Jeavons, P.: Presenting constraints. In: Giese, M., Waaler, A. (eds.) TABLEAUX 2009. LNCS (LNAI), vol.\u00a05607, pp. 1\u201315. Springer, Heidelberg (2009)"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/3-540-61551-2_80","volume-title":"Principles and Practice of Constraint Programming - CP\u201996","author":"P. Jeavons","year":"1996","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: A test for tractability. In: Freuder, E.C. (ed.) CP 1996. LNCS, vol.\u00a01118, pp. 267\u2013281. Springer, Heidelberg (1996)"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1023\/A:1009890709297","volume":"4","author":"P. Jeavons","year":"1999","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: How to determine the expressive power of constraints. Constraints\u00a04, 113\u2013131 (1999)","journal-title":"Constraints"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/j.tcs.2008.06.057","volume":"407","author":"M. Kozik","year":"2008","unstructured":"Kozik, M.: A finite set of functions with an EXPTIME-complete composition problem. Theoret. Comput. Sci.\u00a0407, 330\u2013341 (2008)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2013 CP 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15396-9_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:53:29Z","timestamp":1619787209000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15396-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153952","9783642153969"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15396-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}