{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T19:47:53Z","timestamp":1743018473792,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030757748"},{"type":"electronic","value":"9783030757755"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-75775-5_10","type":"book-chapter","created":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T23:46:09Z","timestamp":1620776769000},"page":"133-146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tractable Combinations of Theories via Sampling"],"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":[[2021,5,12]]},"reference":[{"key":"10_CR1","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":"10_CR2","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-89439-1_4","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"M Bezem","year":"2008","unstructured":"Bezem, M., Nieuwenhuis, R., Rodr\u00edguez-Carbonell, E.: The max-atom problem and its relevance. In: Cervesato, I., Veith, H., Voronkov, A. (eds.) LPAR 2008. LNCS (LNAI), vol. 5330, pp. 47\u201361. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-89439-1_4"},{"key":"10_CR3","unstructured":"Bodirsky, M., Greiner, J.: The complexity of combinations of qualitative constraint satisfaction problems. Log. Methods Comput. Sci. 16(1) (2020). https:\/\/lmcs.episciences.org\/6129"},{"key":"10_CR4","unstructured":"Bodirsky, M., Greiner, J.: Tractable combinations of theories via sampling (2020). https:\/\/arxiv.org\/abs\/2012.01199"},{"key":"10_CR5","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"},{"issue":"4","key":"10_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2528933","volume":"14","author":"M Bodirsky","year":"2013","unstructured":"Bodirsky, M., Macpherson, D., Thapper, J.: Constraint satisfaction tractability from semi-lattice operations on infinite sets. Trans. Comput. Log. (ACM-TOCL) 14(4), 1\u201330 (2013)","journal-title":"Trans. Comput. Log. (ACM-TOCL)"},{"issue":"3","key":"10_CR7","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."},{"issue":"1","key":"10_CR8","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0004-3702(89)90080-5","volume":"41","author":"MC Cooper","year":"1989","unstructured":"Cooper, M.C.: An optimal k-consistency algorithm. Artif. Intell. 41(1), 89\u201395 (1989). https:\/\/doi.org\/10.1016\/0004-3702(89)90080-5","journal-title":"Artif. Intell."},{"key":"10_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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. 1713, pp. 159\u2013173. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-3-540-48085-3_12"},{"issue":"9","key":"10_CR10","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1145\/1995376.1995394","volume":"54","author":"L De Moura","year":"2011","unstructured":"De Moura, L., Bj\u00f8rner, N.: Satisfiability modulo theories: introduction and applications. Commun. ACM 54(9), 69\u201377 (2011). https:\/\/doi.org\/10.1145\/1995376.1995394","journal-title":"Commun. ACM"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1999","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28, 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/BF01116454","volume":"4","author":"MK Gol\u2019dberg","year":"1968","unstructured":"Gol\u2019dberg, M.K., Livshits, E.M.: On minimal universal trees. Math. Notes Acad. Sci. USSR 4, 713\u2013717 (1968). https:\/\/doi.org\/10.1007\/BF01116454","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"10_CR13","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)"},{"issue":"1\u20132","key":"10_CR14","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","volume":"101","author":"P Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D., Cooper, M.: Constraints, consistency and closure. Artif. Intell. 101(1\u20132), 251\u2013265 (1998)","journal-title":"Artif. Intell."},{"key":"10_CR15","first-page":"345","volume":"84","author":"V Lozin","year":"2007","unstructured":"Lozin, V., Rudolf, G.: Minimal universal bipartite graphs. Ars Comb. 84, 345\u2013356 (2007)","journal-title":"Ars Comb."},{"issue":"1","key":"10_CR16","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1017\/S2040618500035139","volume":"7","author":"JW Moon","year":"1965","unstructured":"Moon, J.W.: On minimal n-universal graphs. Proc. Glasgow Math. Assoc. 7(1), 32\u201333 (1965). https:\/\/doi.org\/10.1017\/S2040618500035139","journal-title":"Proc. Glasgow Math. Assoc."},{"issue":"2","key":"10_CR17","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/357073.357079","volume":"1","author":"G Nelson","year":"1979","unstructured":"Nelson, G., Oppen, D.C.: Simplification by cooperating decision procedures. ACM Trans. Program. Lang. Syst. 1(2), 245\u2013257 (1979). https:\/\/doi.org\/10.1145\/357073.357079","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"3","key":"10_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0304-3975(80)90059-6","volume":"12","author":"DC Oppen","year":"1980","unstructured":"Oppen, D.C.: Complexity, convexity and combinations of theories. Theor. Comput. Sci. 12(3), 291\u2013302 (1980). https:\/\/doi.org\/10.1016\/0304-3975(80)90059-6","journal-title":"Theor. Comput. Sci."},{"key":"10_CR19","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/10720084_15","volume-title":"Frontiers of Combining Systems","author":"KU Schulz","year":"2000","unstructured":"Schulz, K.U.: Why combined decision problems are often intractable. In: Kirchner, H., Ringeissen, C. (eds.) FroCoS 2000. LNCS (LNAI), vol. 1794, pp. 217\u2013244. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10720084_15"},{"issue":"1","key":"10_CR20","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0304-3975(01)00332-2","volume":"290","author":"C Tinelli","year":"2003","unstructured":"Tinelli, C., Ringeissen, C.: Unions of non-disjoint theories and combinations of satisfiability procedures. Theor. Comput. Sci. 290(1), 291\u2013353 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(01)00332-2","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Logics in Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-75775-5_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T23:48:27Z","timestamp":1620776907000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-75775-5_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030757748","9783030757755"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-75775-5_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"12 May 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"JELIA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Logics in Artificial Intelligence","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"jelia2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/jelia2021.aau.at\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"27","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the Corona pandemic this event was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}