{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T02:53:33Z","timestamp":1775184813960,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,7,9]],"date-time":"2018-07-09T00:00:00Z","timestamp":1531094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["681988"],"award-info":[{"award-number":["681988"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,7,9]]},"DOI":"10.1145\/3209108.3209156","type":"proceedings-article","created":{"date-parts":[[2018,6,27]],"date-time":"2018-06-27T12:14:43Z","timestamp":1530101683000},"page":"105-114","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP"],"prefix":"10.1145","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Algebra, Technische, Universit\u00e4t Dresden, Dresden, Germany"}]},{"given":"Florent","family":"Madelaine","sequence":"additional","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Aubi\u00e8re, France"}]},{"given":"Antoine","family":"Mottet","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Algebra, Technische, Universit\u00e4t Dresden, Dresden, Germany"}]}],"member":"320","published-online":{"date-parts":[[2018,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the 32nd Annual IEEE Symposium on Logic in Computer Science -- LICS'17.","author":"Barto Libor","year":"2017","unstructured":"Libor Barto , Michael Kompatscher , Miroslav Ol\u0161\u00e1k , Michael Pinsker , and Trung Van Pham . 2017 . The Two Dichotomy Conjectures for Infinite Domain Constraint Satisfaction Problems Are Equivalent . In Proceedings of the 32nd Annual IEEE Symposium on Logic in Computer Science -- LICS'17. Libor Barto, Michael Kompatscher, Miroslav Ol\u0161\u00e1k, Michael Pinsker, and Trung Van Pham. 2017. The Two Dichotomy Conjectures for Infinite Domain Constraint Satisfaction Problems Are Equivalent. In Proceedings of the 32nd Annual IEEE Symposium on Logic in Computer Science -- LICS'17."},{"key":"e_1_3_2_1_2_1","first-page":"1","article-title":"Absorbing subalgebras, cyclic terms and the constraint satisfaction problem","volume":"8","author":"Barto Libor","year":"2012","unstructured":"Libor Barto and Marcin Kozik . 2012 . Absorbing subalgebras, cyclic terms and the constraint satisfaction problem . Logical Methods in Computer Science 8\/1 , 07 (2012), 1 -- 26 . Libor Barto and Marcin Kozik. 2012. Absorbing subalgebras, cyclic terms and the constraint satisfaction problem. Logical Methods in Computer Science 8\/1, 07 (2012), 1--26.","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_2_1_3_1","volume-title":"The wonderland of reflections. Israel Journal of Mathematics","author":"Barto Libor","year":"2017","unstructured":"Libor Barto , Jakub Opr\u0161al , and Michael Pinsker . 2017. The wonderland of reflections. Israel Journal of Mathematics ( 2017 ). To appear. Preprint arXiv:1510.04521. Libor Barto, Jakub Opr\u0161al, and Michael Pinsker. 2017. The wonderland of reflections. Israel Journal of Mathematics (2017). To appear. Preprint arXiv:1510.04521."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934544"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(1:2)2007"},{"key":"e_1_3_2_1_6_1","unstructured":"Manuel Bodirsky. 2012. Complexity Classification in Infinite-Domain Constraint Satisfaction. (2012). M\u00e9moire d'habilitation \u00e0 diriger des recherches Universit\u00e9 Diderot -- Paris 7. Available at arXiv:1201.0856v8.  Manuel Bodirsky. 2012. Complexity Classification in Infinite-Domain Constraint Satisfaction. (2012). M\u00e9moire d'habilitation \u00e0 diriger des recherches Universit\u00e9 Diderot -- Paris 7. Available at arXiv:1201.0856v8."},{"key":"e_1_3_2_1_7_1","volume-title":"Ramsey Classes: Examples and Constructions. In Surveys in Combinatorics","author":"Bodirsky Manuel","year":"2015","unstructured":"Manuel Bodirsky . 2015 . Ramsey Classes: Examples and Constructions. In Surveys in Combinatorics . London Mathematical Society Lecture Note Series 424. Cambridge University Press . Invited survey article for the British Combinatorial Conference. Manuel Bodirsky. 2015. Ramsey Classes: Examples and Constructions. In Surveys in Combinatorics. London Mathematical Society Lecture Note Series 424. Cambridge University Press. Invited survey article for the British Combinatorial Conference."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.05.012"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934515"},{"key":"e_1_3_2_1_10_1","volume-title":"A Dichotomy for First-Order Reducts of Unary Structures. Logical Methods of Computer Science","author":"Bodirsky Manuel","year":"2018","unstructured":"Manuel Bodirsky and Antoine Mottet . 2018. A Dichotomy for First-Order Reducts of Unary Structures. Logical Methods of Computer Science ( 2018 ). To appear. Manuel Bodirsky and Antoine Mottet. 2018. A Dichotomy for First-Order Reducts of Unary Structures. Logical Methods of Computer Science (2018). To appear."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"e_1_3_2_1_12_1","unstructured":"Manuel Bodirsky and Michael Pinsker. 2016. Canonical Functions: a Proof via Topological Dynamics. (2016). Preprint available under http:\/\/arxiv.org\/abs\/1610.09660.  Manuel Bodirsky and Michael Pinsker. 2016. Canonical Functions: a Proof via Topological Dynamics. (2016). Preprint available under http:\/\/arxiv.org\/abs\/1610.09660."},{"key":"e_1_3_2_1_13_1","unstructured":"Manuel Bodirsky Michael Pinsker and Andr\u00e1s Pongr\u00e1cz. 2014. Projective clone homomorphisms. (2014). Preprint arXiv:1409.4601.  Manuel Bodirsky Michael Pinsker and Andr\u00e1s Pongr\u00e1cz. 2014. Projective clone homomorphisms. (2014). Preprint arXiv:1409.4601."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_1_15_1","volume-title":"Bulatov and Peter Jeavons","author":"Andrei","year":"2001","unstructured":"Andrei A. Bulatov and Peter Jeavons . 2001 . Algebraic Structures in Combinatorial Problems. Technical report MATH-AL-4-2001, Technische Universit\u00e4t Dresden . (2001). Andrei A. Bulatov and Peter Jeavons. 2001. Algebraic Structures in Combinatorial Problems. Technical report MATH-AL-4-2001, Technische Universit\u00e4t Dresden. (2001)."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1998.0641"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167245"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_1_21_1","unstructured":"J. Hubi\u010dka and J. Ne\u0161et\u0159il. 2016. All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms). (2016). arXiv:1606.07979v2.  J. Hubi\u010dka and J. Ne\u0161et\u0159il. 2016. All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms). (2016). arXiv:1606.07979v2."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2405-4"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the 18th International Conference on Database Theory (ICDT15)","author":"Lutz Carsten","year":"2015","unstructured":"Carsten Lutz and Frank Wolter . 2015 . On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems . In Proceedings of the 18th International Conference on Database Theory (ICDT15) . Carsten Lutz and Frank Wolter. 2015. On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems. In Proceedings of the 18th International Conference on Database Theory (ICDT15)."},{"key":"e_1_3_2_1_24_1","volume-title":"Constraint satisfaction problems and related logic. PhD-thesis","author":"Madelaine Florent","unstructured":"Florent Madelaine . 2003. Constraint satisfaction problems and related logic. PhD-thesis , University of Leicester. (2003) . Florent Madelaine. 2003. Constraint satisfaction problems and related logic. PhD-thesis, University of Leicester. (2003)."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/050634840"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"event":{"name":"LICS '18: 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Oxford United Kingdom","acronym":"LICS '18","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"]},"container-title":["Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209108.3209156","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209108.3209156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:07Z","timestamp":1750212427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209108.3209156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,9]]},"references-count":26,"alternative-id":["10.1145\/3209108.3209156","10.1145\/3209108"],"URL":"https:\/\/doi.org\/10.1145\/3209108.3209156","relation":{},"subject":[],"published":{"date-parts":[[2018,7,9]]},"assertion":[{"value":"2018-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}