{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T15:34:16Z","timestamp":1725982456950},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319942049"},{"type":"electronic","value":"9783319942056"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94205-6_18","type":"book-chapter","created":{"date-parts":[[2018,6,29]],"date-time":"2018-06-29T16:22:50Z","timestamp":1530289370000},"page":"263-278","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity of Combinations of Qualitative Constraint Satisfaction Problems"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Greiner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,30]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Ackerman, N., Freer, C., Patel, R.: Invariant measures concentrated on countable structures. In: Forum of Mathematics Sigma, vol. 4 (2016)","DOI":"10.1017\/fms.2016.15"},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/3-540-45406-3_3","volume-title":"Constraints in Computational Logics","author":"F Baader","year":"2001","unstructured":"Baader, F., Schulz, K.U.: Combining constraint solving. In: Goos, G., Hartmanis, J., van Leeuwen, J., Comon, H., March\u00e9, C., Treinen, R. (eds.) CCL 1999. LNCS, vol. 2002, pp. 104\u2013158. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45406-3_3"},{"key":"18_CR3","unstructured":"Barto, L., Kompatscher, M., Ol\u0161\u00e1k, M., Pinsker, M., Pham, T.V.: The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems. In: Proceedings of the 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017 (2017). Preprint arXiv:1612.07551"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s11856-017-1621-9","volume":"223","author":"L Barto","year":"2017","unstructured":"Barto, L., Opr\u0161al, J., Pinsker, M.: The wonderland of reflections. Israel J. Math. 223, 363\u2013398 (2017). Preprint arXiv:1510.04521","journal-title":"Israel J. Math."},{"key":"18_CR5","unstructured":"Barto, L., Pinsker, M.: The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In: Proceedings of the 31st Annual IEEE Symposium on Logic in Computer Science, LICS 2016, pp. 615\u2013622 (2016). Preprint arXiv:1602.04353"},{"key":"18_CR6","unstructured":"Bodirsky, M.: Complexity classification in infinite-domain constraint satisfaction. M\u00e9moire d\u2019habilitation \u00e0 diriger des recherches, Universit\u00e9 Diderot - Paris 7. arXiv:1201.0856 (2012)"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Greiner, J.: Complexity of combinations of qualitative constraint satisfaction problems. Preprint arXiv:1801.05965 (2018)","DOI":"10.1007\/978-3-319-94205-6_18"},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-540-70583-3_16","volume-title":"Automata, Languages and Programming","author":"M Bodirsky","year":"2008","unstructured":"Bodirsky, M., Grohe, M.: Non-dichotomies in constraint satisfaction complexity. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 184\u2013196. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70583-3_16"},{"key":"18_CR9","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1613\/jair.5260","volume":"58","author":"M Bodirsky","year":"2017","unstructured":"Bodirsky, M., Jonsson, P.: A model-theoretic view on qualitative constraint reasoning. J. Artif. Intell. Res. 58, 339\u2013385 (2017)","journal-title":"J. Artif. Intell. Res."},{"issue":"3","key":"18_CR10","first-page":"23","volume":"18","author":"M Bodirsky","year":"2017","unstructured":"Bodirsky, M., Jonsson, P., Pham, T.V.: The complexity of phylogeny constraint satisfaction problems. ACM Trans. Comput. Log. (TOCL) 18(3), 23 (2017). An extended abstract appeared in the conference STACS 2016","journal-title":"ACM Trans. Comput. Log. (TOCL)"},{"issue":"2","key":"18_CR11","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/s00224-007-9083-9","volume":"3","author":"M Bodirsky","year":"2008","unstructured":"Bodirsky, M., K\u00e1ra, J.: The complexity of equality constraint languages. Theory Comput. Syst. 3(2), 136\u2013158 (2008). A conference version appeared in the proceedings of Computer Science Russia, CSR 2006","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"18_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1667053.1667058","volume":"57","author":"M Bodirsky","year":"2009","unstructured":"Bodirsky, M., K\u00e1ra, J.: The complexity of temporal constraint satisfaction problems. J. ACM 57(2), 1\u201341 (2009). An extended abstract appeared in the Proceedings of the Symposium on Theory of Computing, STOC","journal-title":"J. ACM"},{"issue":"3","key":"18_CR13","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1740582.1740583","volume":"11","author":"M Bodirsky","year":"2010","unstructured":"Bodirsky, M., K\u00e1ra, J.: A fast algorithm and Datalog inexpressibility for temporal reasoning. ACM Trans. Comput. Log. 11(3), 15 (2010)","journal-title":"ACM Trans. Comput. Log."},{"key":"18_CR14","unstructured":"Bodirsky, M., Mottet, A.: Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction. In: Proceedings of the 31st Annual IEEE Symposium on Logic in Computer Science, LICS 2016, pp. 623\u2013632 (2016). Preprint ArXiv:1601.04520"},{"issue":"3","key":"18_CR15","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1093\/logcom\/exi083","volume":"16","author":"M Bodirsky","year":"2006","unstructured":"Bodirsky, M., Ne\u0161et\u0159il, J.: Constraint satisfaction with countable homogeneous templates. J. Log. Comput. 16(3), 359\u2013373 (2006)","journal-title":"J. Log. Comput."},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"2527","DOI":"10.1090\/S0002-9947-2014-05975-8","volume":"367","author":"M Bodirsky","year":"2015","unstructured":"Bodirsky, M., Pinsker, M.: Topological Birkhoff. Trans. Am. Math. Soc. 367, 2527\u20132549 (2015)","journal-title":"Trans. Am. Math. Soc."},{"key":"18_CR17","unstructured":"Bodirsky, M., Pinsker, M., Pongr\u00e1cz, A.: Projective clone homomorphisms. J. Symb. Log. (2014, accepted for publication). Preprint arXiv:1409.4601"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/11814771_42","volume-title":"Automated Reasoning","author":"MP Bonacina","year":"2006","unstructured":"Bonacina, M.P., Ghilardi, S., Nicolini, E., Ranise, S., Zucchelli, D.: Decidability and undecidability results for Nelson-Oppen and rewrite-based decision procedures. In: Furbach, U., Shankar, N. (eds.) IJCAR 2006. LNCS, vol. 4130, pp. 513\u2013527. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11814771_42"},{"issue":"1","key":"18_CR19","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/2490253","volume":"15","author":"R Bruttomesso","year":"2014","unstructured":"Bruttomesso, R., Ghilardi, S., Ranise, S.: Quantifier-free interpolation in combinations of equality interpolating theories. ACM Trans. Comput. Log. 15(1), 5 (2014)","journal-title":"ACM Trans. Comput. Log."},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. FOCS 2017 (2017, accepted for publication). arXiv:1703.03021","DOI":"10.1109\/FOCS.2017.37"},{"key":"18_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511549809","volume-title":"Oligomorphic Permutation Groups","author":"PJ Cameron","year":"1990","unstructured":"Cameron, P.J.: Oligomorphic Permutation Groups. Cambridge University Press, Cambridge (1990)"},{"issue":"2","key":"18_CR22","doi-asserted-by":"crossref","first-page":"2","DOI":"10.37236\/1674","volume":"9","author":"PJ Cameron","year":"2002","unstructured":"Cameron, P.J.: Homogeneous permutations. Electron. J. Comb. 9(2), 2 (2002)","journal-title":"Electron. J. Comb."},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Cherlin, G.: The Classification of Countable Homogeneous Directed Graphs and Countable Homogeneous $$n$$-Tournaments, vol. 131, no. 621. AMS Memoirs, New York, January 1998","DOI":"10.1090\/memo\/0621"},{"key":"18_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3","volume-title":"Complexity of Constraints","year":"2008","unstructured":"Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.): Complexity of Constraints. LNCS, vol. 5250. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-92800-3"},{"key":"18_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574","volume-title":"Model Theory","author":"W Hodges","year":"1993","unstructured":"Hodges, W.: Model Theory. Cambridge University Press, Cambridge (1993)"},{"key":"18_CR26","volume-title":"A Shorter Model Theory","author":"W Hodges","year":"1997","unstructured":"Hodges, W.: A Shorter Model Theory. Cambridge University Press, Cambridge (1997)"},{"key":"18_CR27","unstructured":"Kompatscher, M., Pham, T.V.: A complexity dichotomy for poset constraint satisfaction. In: 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017. Leibniz International Proceedings in Informatics, LIPIcs, vol. 66, pp. 47:1\u201347:12 (2017)"},{"key":"18_CR28","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1090\/S0002-9947-1984-0743728-1","volume":"284","author":"AH Lachlan","year":"1984","unstructured":"Lachlan, A.H.: Countable homogeneous tournaments. TAMS 284, 431\u2013461 (1984)","journal-title":"TAMS"},{"issue":"2","key":"18_CR29","first-page":"1","volume":"22","author":"J Linman","year":"2015","unstructured":"Linman, J., Pinsker, M.: Permutations on the random permutation. Electron. J. Comb. 22(2), 1\u201322 (2015)","journal-title":"Electron. J. Comb."},{"issue":"2","key":"18_CR30","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1145\/322186.322198","volume":"27","author":"G Nelson","year":"1980","unstructured":"Nelson, G., Oppen, D.C.: Fast decision procedures based on congruence closure. J. ACM 27(2), 356\u2013364 (1980)","journal-title":"J. ACM"},{"key":"18_CR31","doi-asserted-by":"crossref","unstructured":"Zhuk, D.: The proof of CSP dichotomy conjecture. FOCS 2017 (2017, accepted for publication). arXiv:1704.01914","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["Lecture Notes in Computer Science","Automated Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94205-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T19:17:18Z","timestamp":1604517438000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-94205-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319942049","9783319942056"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94205-6_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}