{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:42:31Z","timestamp":1774946551091,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"S1","license":[{"start":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T00:00:00Z","timestamp":1665360000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T00:00:00Z","timestamp":1665360000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s00493-022-4918-1","type":"journal-article","created":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T11:55:12Z","timestamp":1665402912000},"page":"997-1010","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Maximal Digraphs with Respect to Primitive Positive Constructability"],"prefix":"10.1007","volume":"42","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Starke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,10]]},"reference":[{"key":"4918_CR1","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jctb.2000.1970","volume":"80","author":"J Ne\u0161et\u0159il","year":"2000","unstructured":"J. Ne\u0161et\u0159il and C. Tardif: Duality theorems for finite structures, Journal of Combinatorial Theory, Series B 80 (2000), 80\u201397.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4918_CR2","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"P. Hell and J. Ne\u0161et\u0159il: On the complexity of H-coloring, Journal of Combinatorial Theory, Series B 48 (1990), 92\u2013110.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4918_CR3","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1999","unstructured":"T. Feder and M. Y. Vardi: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM Journal on Computing 28 (1999), 57\u2013104.","journal-title":"SIAM Journal on Computing"},{"key":"4918_CR4","doi-asserted-by":"crossref","unstructured":"J. Bulin, D. Delic, M. Jackson and T. Niven: A finer reduction of constraint problems to digraphs, Log. Methods Comput. Sci. 11 (2015).","DOI":"10.2168\/LMCS-11(4:18)2015"},{"key":"4918_CR5","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov: A dichotomy theorem for nonuniform CSPs, in: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, 319\u2013330, 2017.","DOI":"10.1109\/FOCS.2017.37"},{"key":"4918_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3402029","volume":"67","author":"D Zhuk","year":"2020","unstructured":"D. Zhuk: A proof of the CSP dichotomy conjecture, J. ACM 67 (2020), 1\u201378.","journal-title":"J. ACM"},{"key":"4918_CR7","doi-asserted-by":"crossref","unstructured":"V. Dalmau: Linear datalog and bounded path duality of relational structures, Logical Methods in Computer Science 1 (2005).","DOI":"10.2168\/LMCS-1(1:5)2005"},{"key":"4918_CR8","doi-asserted-by":"crossref","unstructured":"L. Egri, B. Larose and P. Tesson: Symmetric datalog and constraint satisfaction problems in logspace, in: Proceedings of the Symposium on Logic in Computer Science (LICS), 193\u2013202, 2007.","DOI":"10.1109\/LICS.2007.47"},{"key":"4918_CR9","unstructured":"A. Kazda: n-permutability and linear Datalog implies symmetric Datalog, Log. Methods Comput. Sci. 14 (2018)."},{"key":"4918_CR10","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s11856-017-1621-9","volume":"223","author":"L Barto","year":"2018","unstructured":"L. Barto, J. Opr\u0161al and M. Pinsker: The wonderland of reflections, Israel Journal of Mathematics 223 (2018), 363\u2013398.","journal-title":"Israel Journal of Mathematics"},{"key":"4918_CR11","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1142\/S0218196721500442","volume":"31","author":"M Bodirsky","year":"2021","unstructured":"M. Bodirsky, F. Starke and A. Vucaj: Smooth digraphs modulo primitive positive constructability and cyclic loop conditions. International Journal on Algebra and Computation 31 (2021), 939\u2013967.","journal-title":"International Journal on Algebra and Computation"},{"key":"4918_CR12","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and A. Vucaj: Two-element structures modulo primitive positive constructability, Algebra Universalis, 81, 2020.","DOI":"10.1007\/s00012-020-0647-8"},{"key":"4918_CR13","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P Hell","year":"2004","unstructured":"P. Hell and J. Ne\u0161et\u0159il: Graphs and Homomorphisms, Oxford University Press, Oxford, 2004."},{"key":"4918_CR14","first-page":"1","volume":"3","author":"M Bodirsky","year":"2007","unstructured":"M. Bodirsky: Cores of countably categorical structures, Logical Methods in Computer Science (LMCS) 3 (2007), 1\u201316.","journal-title":"Logical Methods in Computer Science (LMCS)"},{"key":"4918_CR15","doi-asserted-by":"publisher","first-page":"P1.47","DOI":"10.37236\/4419","volume":"22","author":"C Carvalho","year":"2015","unstructured":"C. Carvalho, L. Egri, M. Jackson and T. Niven: On Maltsev digraphs, Electr. J. Comb. 22 (2015), P1.47.","journal-title":"Electr. J. Comb."},{"key":"4918_CR16","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1006\/jctb.1996.0068","volume":"68","author":"B L Bauslaugh","year":"1996","unstructured":"B. L. Bauslaugh: Cores and compactness of infinite directed graphs, Journal of Combinatorial Theory, Series B 68 (1996), 255\u2013276.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4918_CR17","unstructured":"M. Bodirsky, A. Mottet, M. Ol\u0161\u00e1k, J. Opr\u0161al, M. Pinsker and R. Willard: \u03c9-categorical structures avoiding height 1 identities, Transactions of the American Mathematical Society, accepted."},{"key":"4918_CR18","doi-asserted-by":"publisher","first-page":"1395","DOI":"10.1142\/S0218196716500600","volume":"26","author":"M Jackson","year":"2016","unstructured":"M. Jackson, T. Kowalski and T. Niven: Complexity and polymorphisms for digraph constraint problems under some basic constructions, Int. J. Algebra Comput. 26 (2016), 1395\u20131433.","journal-title":"Int. J. Algebra Comput."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-022-4918-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-022-4918-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-022-4918-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T16:32:30Z","timestamp":1675355550000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-022-4918-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,10]]},"references-count":18,"journal-issue":{"issue":"S1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["4918"],"URL":"https:\/\/doi.org\/10.1007\/s00493-022-4918-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,10]]},"assertion":[{"value":"15 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}