{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:34:24Z","timestamp":1787510064605,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540323013","type":"print"},{"value":"9783540322887","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11672142_53","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T03:27:54Z","timestamp":1141097274000},"page":"646-659","source":"Crossref","is-referenced-by-count":19,"title":["Datalog and Constraint Satisfaction with Infinite Templates"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"V\u00edctor","family":"Dalmau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"53_CR1","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0012-365X(97)84217-3","volume":"165","author":"D. Achlioptas","year":"1997","unstructured":"Achlioptas, D.: The complexity of G-free colourability. Discrete Mathematics\u00a0165, 21\u201330 (1997)","journal-title":"Discrete Mathematics"},{"issue":"4","key":"53_CR2","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1305\/ndjfl\/1040408612","volume":"35","author":"H. Andr\u00e9ka","year":"1994","unstructured":"Andr\u00e9ka, H., Maddux, R.D.: Representations for small relation algebras. Notre Dame Journal of Formal Logic\u00a035(4), 550\u2013562 (1994)","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"53_CR3","doi-asserted-by":"crossref","unstructured":"Atserias, A.: On digraph coloring problems and treewidth duality. In: 20th IEEE Symposium on Logic in Computer Science (LICS), pp. 106\u2013115 (2005)","DOI":"10.1109\/LICS.2005.31"},{"key":"53_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-540-31856-9_9","volume-title":"STACS 2005","author":"M. Bodirsky","year":"2005","unstructured":"Bodirsky, M.: The core of a countably categorical structure. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 100\u2013110. Springer, Heidelberg (2005)"},{"key":"53_CR5","unstructured":"Bodirsky, M., Chen, H.: Oligomorphic clones. Preprint (2005)"},{"key":"53_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-540-45220-1_5","volume-title":"Computer Science Logic","author":"M. Bodirsky","year":"2003","unstructured":"Bodirsky, M., Ne\u0161et\u0159il, J.: Constraint satisfaction with countable homogeneous templates. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol.\u00a02803, pp. 44\u201357. Springer, Heidelberg (2003)"},{"key":"53_CR7","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.G.: Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing\u00a034, 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"53_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511549809","volume-title":"Oligomorphic Permutation Groups","author":"P.J. Cameron","year":"1990","unstructured":"Cameron, P.J.: Oligomorphic Permutation Groups. Cambridge University Press, Cambridge (1990)"},{"key":"53_CR9","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: Proceddings of STOC 1977, pp. 77\u201390 (1977)","DOI":"10.1145\/800105.803397"},{"key":"53_CR10","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1006\/aama.1998.0641","volume":"22","author":"G. Cherlin","year":"1999","unstructured":"Cherlin, G., Shelah, S., Shi, N.: Universal graphs with forbidden subgraphs and algebraic closure. Advances in Applied Mathematics\u00a022, 454\u2013491 (1999)","journal-title":"Advances in Applied Mathematics"},{"issue":"4","key":"53_CR11","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1215\/ijm\/1255988065","volume":"34","author":"J. Covington","year":"1990","unstructured":"Covington, J.: Homogenizable relational structures. Illinois Journal of Mathematics\u00a034(4), 731\u2013743 (1990)","journal-title":"Illinois Journal of Mathematics"},{"key":"53_CR12","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.artint.2004.02.003","volume":"156","author":"M. Cristiani","year":"2004","unstructured":"Cristiani, M., Hirsch, R.: The complexity of the constraint satisfaction problem for small relation algebras. Artificial Intelligence Journal\u00a0156, 177\u2013196 (2004)","journal-title":"Artificial Intelligence Journal"},{"issue":"1-2","key":"53_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s10472-005-1810-9","volume":"44","author":"V. Dalmau","year":"2005","unstructured":"Dalmau, V.: A new tractable class of constraint satisfaction problems. Ann. Math. Artif. Intell.\u00a044(1-2), 61\u201385 (2005)","journal-title":"Ann. Math. Artif. Intell."},{"key":"53_CR14","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Krokhin, A.A., Larose, B.: First-order definable retraction problems for posets and reflexive graph. In: LICS 2004, pp. 232\u2013241 (2004)","DOI":"10.1109\/LICS.2004.1319617"},{"key":"53_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/978-3-540-48085-3_12","volume-title":"Principles and Practice of Constraint Programming \u2013 CP\u201999","author":"V. Dalmau","year":"1999","unstructured":"Dalmau, V., Pearson, J.: Closure functions and width 1 problems. In: Jaffar, J. (ed.) CP 1999. LNCS, vol.\u00a01713, pp. 159\u2013173. Springer, Heidelberg (1999)"},{"key":"53_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s10462-004-5899-8","volume":"23","author":"I. D\u00fcntsch","year":"2005","unstructured":"D\u00fcntsch, I.: Relation algebras and their application in temporal and spatial reasoning. Artificial Intelligence Review\u00a023, 315\u2013357 (2005)","journal-title":"Artificial Intelligence Review"},{"key":"53_CR17","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"53_CR18","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"Feder, T., Vardi, M.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing\u00a028, 57\u2013104 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"53_CR19","doi-asserted-by":"crossref","unstructured":"Feder, T., Vardi, M.: Homomorphism closed vs. existential positive. In: Feder, T., Vardi, M. (eds.) Symposium on Logic in Computer Science (LICS 2003), pp. 311\u2013320 (2003)","DOI":"10.1109\/LICS.2003.1210071"},{"key":"53_CR20","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. Journal of Combinatorial Theory, Series B\u00a048, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"3","key":"53_CR21","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1093\/logcom\/7.3.309","volume":"7","author":"R. Hirsch","year":"1997","unstructured":"Hirsch, R.: Expressive power and complexity in algebraic logic. Journal of Logic and Computation\u00a07(3), 309\u2013351 (1997)","journal-title":"Journal of Logic and Computation"},{"key":"53_CR22","volume-title":"A shorter model theory","author":"W. Hodges","year":"1997","unstructured":"Hodges, W.: A shorter model theory. Cambridge University Press, Cambridge (1997)"},{"issue":"1-2","key":"53_CR23","first-page":"251","volume":"101","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D., Cooper, M.: Constraints, consistency and closure. AI\u00a0101(1-2), 251\u2013265 (1998)","journal-title":"AI"},{"issue":"4","key":"53_CR24","doi-asserted-by":"publisher","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 ACM\u00a044(4), 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"53_CR25","doi-asserted-by":"crossref","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. In: Proceedings of PODS 1998, pp. 205\u2013213 (1998)","DOI":"10.1145\/275487.275511"},{"key":"53_CR26","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/1-4020-3817-8_8","volume":"207","author":"A. Krokhin","year":"2005","unstructured":"Krokhin, A., Bulatov, A., Jeavons, P.: The complexity of constraint satisfaction: An algebraic approach (survey paper). Structural Theory of Automata, Semigroups and Universal Algebra, NATO Science Series II: Mathematics, Physics, and Chemistry\u00a0207, 181\u2013213 (2005)","journal-title":"Structural Theory of Automata, Semigroups and Universal Algebra, NATO Science Series II: Mathematics, Physics, and Chemistry"},{"key":"53_CR27","unstructured":"Kun, G.: Every problem in MMSNP is polynomial time equivalent to a CSP. Personal communication (2005)"},{"issue":"3","key":"53_CR28","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1145\/176584.176585","volume":"41","author":"P.B. Ladkin","year":"1994","unstructured":"Ladkin, P.B., Maddux, R.D.: On binary constraint problems. Journal of the Association for Computing Machinery\u00a041(3), 435\u2013469 (1994)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"53_CR29","first-page":"339","volume":"7","author":"B. Larose","year":"2001","unstructured":"Larose, B., Tardif, C.: Strongly rigid graphs and projectivity. Multiple-Valued Logic\u00a07, 339\u2013361 (2001)","journal-title":"Multiple-Valued Logic"},{"key":"53_CR30","unstructured":"Madelaine, F., Stewart, I.A.: Some problems not definable using structure homomorphisms. MCS technical report. University of Leicester\u00a099(18) (1999)"},{"key":"53_CR31","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jctb.2000.1970","volume":"80","author":"J. Ne\u0161et\u0159il","year":"2000","unstructured":"Ne\u0161et\u0159il, J., Tardif, C.: Duality theorems for finite structures (characterising gaps and good characterisations). Journal of Combininatorial Theory Series B\u00a080, 80\u201397 (2000)","journal-title":"Journal of Combininatorial Theory Series B"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,12]],"date-time":"2019-03-12T03:29:35Z","timestamp":1552361375000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/11672142_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}