{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T15:52:58Z","timestamp":1790524378523,"version":"4.1.0"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030514655","type":"print"},{"value":"9783030514662","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","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":[[2020]]},"DOI":"10.1007\/978-3-030-51466-2_13","type":"book-chapter","created":{"date-parts":[[2020,6,23]],"date-time":"2020-06-23T09:03:46Z","timestamp":1592903026000},"page":"149-162","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["ASNP: A Tame Fragment of Existential Second-Order Logic"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon","family":"Kn\u00e4uer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florian","family":"Starke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,6,24]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Barto, L., Kompatscher, M., Ol\u0161\u00e1k, M., Pham, T.V., Pinsker, M.: Equations in oligomorphic clones and the constraint satisfaction problem for $$\\omega $$-categorical structures. J. Math. Logic, 19(2), #1950010 (2019). An extended abstract appeared at the Proceedings of the 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science - LICS\u201917","DOI":"10.1142\/S0219061319500107"},{"key":"13_CR2","unstructured":"Barto, L., Pinsker, M.: The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In: Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science, LICS 2016, pp. 615\u2013622 (2016). Preprint arXiv:1602.04353"},{"issue":"4","key":"13_CR3","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/2661643","volume":"39","author":"M Bienvenu","year":"2014","unstructured":"Bienvenu, M., ten Cate, B., Lutz, C., Wolter, F.: Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP. ACM Trans. Database Syst. 39(4), 33 (2014)","journal-title":"ACM Trans. Database Syst."},{"key":"13_CR4","unstructured":"Bodirsky, M.: Constraint satisfaction with infinite domains. Dissertation, Humboldt-Universit\u00e4t zu Berlin (2004)"},{"key":"13_CR5","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":"13_CR6","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jcss.2012.05.012","volume":"79","author":"M Bodirsky","year":"2013","unstructured":"Bodirsky, M., Dalmau, V.: Datalog and constraint satisfaction with infinite templates. J. Comput. Syst. Sci. 79, 79\u2013100 (2013). A preliminary version appeared in the proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201905)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR7","unstructured":"Bodirsky, M., Madelaine, F., Mottet, A.: A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP. In: Proceedings of the Symposium on Logic in Computer Science (LICS), pp. 105\u2013114 (2018). Preprint available under arXiv:1802.03255"},{"key":"13_CR8","unstructured":"Bodirsky, M., Pinsker, M., Pongr\u00e1cz, A.: Projective clone homomorphisms. J. Symb. Logic (2014). Preprint arXiv:1409.4601"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Rydval, J.: Temporal constraint satisfaction problems in fixed point logic (2019). Preprint","DOI":"10.1145\/3373718.3394750"},{"key":"13_CR10","unstructured":"Braunfeld, S.: Towards the undecidability of atomicity for permutation classes via the undecidability of joint embedding for hereditary graph classes (2019). Preprint available at arXiv:1903.11932"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15\u201317 October 2017, pp. 319\u2013330 (2017)","DOI":"10.1109\/FOCS.2017.37"},{"key":"13_CR12","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. Adv. Appl. Math. 22, 454\u2013491 (1999)","journal-title":"Adv. Appl. Math."},{"key":"13_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press, New York (2012)"},{"key":"13_CR14","first-page":"43","volume":"7","author":"R Fagin","year":"1974","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. Complex. Comput. 7, 43\u201373 (1974)","journal-title":"Complex. Comput."},{"key":"13_CR15","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":"13_CR16","unstructured":"Feder, T., Vardi, M.Y.: Homomorphism closed vs. existential positive. In: Proceedings of the Symposium on Logic in Computer Science (LICS), pp. 311\u2013320 (2003)"},{"issue":"4","key":"13_CR17","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1016\/j.ejc.2007.11.017","volume":"29","author":"J Foniok","year":"2008","unstructured":"Foniok, J., Ne\u0161et\u0159il, J.: Generalised dualities and maximal finite antichains in the homomorphism order of relational structures. Eur. J. Combin. 29(4), 881\u2013899 (2008)","journal-title":"Eur. J. Combin."},{"key":"13_CR18","volume-title":"A Guide to NP-Completeness","author":"M Garey","year":"1978","unstructured":"Garey, M., Johnson, D.: A Guide to NP-Completeness. CSLI Press, Stanford (1978)"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The quest for a logic capturing PTIME. In: Proceedings of ACM\/IEEE Symposium on Logic in Computer Science (LICS), pp. 267\u2013271 (2008)","DOI":"10.1109\/LICS.2008.11"},{"key":"13_CR20","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BFb0099486","volume-title":"Computation and Proof Theory","author":"Y Gurevich","year":"1984","unstructured":"Gurevich, Y.: Toward logic tailored for computational complexity. In: B\u00f6rger, E., Oberschelp, W., Richter, M.M., Schinzel, B., Thomas, W. (eds.) Computation and Proof Theory. LNM, vol. 1104, pp. 175\u2013216. Springer, Heidelberg (1984). https:\/\/doi.org\/10.1007\/BFb0099486"},{"key":"13_CR21","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":"2\u20133","key":"13_CR22","first-page":"229","volume":"27","author":"J Hubi\u010dka","year":"2016","unstructured":"Hubi\u010dka, J., Ne\u0161et\u0159il, J.: Homomorphism and embedding universal structures for restricted classes. Multiple-Valued Logic Soft Comput. 27(2\u20133), 229\u2013253 (2016). arXiv:0909.4939","journal-title":"Multiple-Valued Logic Soft Comput."},{"issue":"3","key":"13_CR23","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s00493-013-2405-4","volume":"33","author":"G Kun","year":"2013","unstructured":"Kun, G.: Constraints, MMSNP, and expander relational structures. Combinatorica 33(3), 335\u2013347 (2013). https:\/\/doi.org\/10.1007\/s00493-013-2405-4","journal-title":"Combinatorica"},{"issue":"1","key":"13_CR24","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"RE Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. ACM 22(1), 155\u2013171 (1975)","journal-title":"J. ACM"},{"key":"13_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/11874683_31","volume-title":"Computer Science Logic","author":"F Madelaine","year":"2006","unstructured":"Madelaine, F.: Universal structures and the logic of forbidden patterns. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 471\u2013485. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11874683_31"},{"key":"13_CR26","unstructured":"Zhuk, D.: A proof of CSP dichotomy conjecture. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15\u201317 October 2017, pp. 331\u2013342 (2017). https:\/\/arxiv.org\/abs\/1704.01914"}],"container-title":["Lecture Notes in Computer Science","Beyond the Horizon of Computability"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-51466-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,9]],"date-time":"2021-03-09T13:08:38Z","timestamp":1615295318000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-51466-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030514655","9783030514662"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-51466-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"24 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fisciano","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cie2020.wordpress.com\/","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":"72","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":"28","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":"5","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":"39% - 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":"7","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the coronavirus pandemic.","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)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}