{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T22:02:23Z","timestamp":1771020143710,"version":"3.50.1"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030435196","type":"print"},{"value":"9783030435202","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":"https:\/\/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":"https:\/\/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-43520-2_3","type":"book-chapter","created":{"date-parts":[[2020,3,31]],"date-time":"2020-03-31T23:08:28Z","timestamp":1585696108000},"page":"31-46","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Hardness of Network Satisfaction for Relation Algebras with Normal Representations"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[]},{"given":"Simon","family":"Kn\u00e4uer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,1]]},"reference":[{"issue":"11","key":"3_CR1","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"JF Allen","year":"1983","unstructured":"Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832\u2013843 (1983)","journal-title":"Commun. ACM"},{"issue":"4","key":"3_CR2","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1305\/ndjfl\/1040408612","volume":"35","author":"H Andr\u00e9ka","year":"1994","unstructured":"Andr\u00e9ka, H., Maddux, R.D.: Representations for small relation algebras. Notre Dame J. Formal Log. 35(4), 550\u2013562 (1994)","journal-title":"Notre Dame J. Formal Log."},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Barto, L.: The dichotomy for conservative constraint satisfaction problems revisited. In: Proceedings of the Symposium on Logic in Computer Science (LICS), Toronto, Canada (2011)","DOI":"10.1109\/LICS.2011.25"},{"key":"3_CR4","doi-asserted-by":"publisher","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."},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.artint.2006.12.004","volume":"171","author":"M Bodirsky","year":"2007","unstructured":"Bodirsky, M., Kutz, M.: Determining the consistency of partial tree descriptions. Artif. Intell. 171, 185\u2013196 (2007)","journal-title":"Artif. Intell."},{"issue":"07","key":"3_CR6","first-page":"1","volume":"8\/1","author":"L Barto","year":"2012","unstructured":"Barto, L., Kozik, M.: Absorbing subalgebras, cyclic terms and the constraint satisfaction problem. Log. Methods Comput. Sci. 8\/1(07), 1\u201326 (2012)","journal-title":"Log. Methods Comput. Sci."},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Barto, L., Kompatscher, M., Ol\u0161\u00e1k, M., Van Pham, T., Pinsker, M.: 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","DOI":"10.1109\/LICS.2017.8005128"},{"issue":"4","key":"3_CR8","doi-asserted-by":"publisher","first-page":"1224","DOI":"10.1137\/16M1082974","volume":"48","author":"M Bodirsky","year":"2019","unstructured":"Bodirsky, M., Martin, B., Pinsker, M., Pongr\u00e1cz, A.: Constraint satisfaction problems for reducts of homogeneous graphs. SIAM J. Comput. 48(4), 1224\u20131264 (2019). A conference version appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pp. 119:1\u2013119:14","journal-title":"SIAM J. Comput."},{"issue":"3","key":"3_CR9","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":"3_CR10","doi-asserted-by":"crossref","unstructured":"Bodirsky, M.: Finite relation algebras with normal representations. In: Relational and Algebraic Methods in Computer Science - 17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29 \u2013 November 1, 2018, Proceedings, pp. 3\u201317 (2018)","DOI":"10.1007\/978-3-030-02149-8_1"},{"issue":"1","key":"3_CR11","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s11856-017-1621-9","volume":"223","author":"L Barto","year":"2018","unstructured":"Barto, L., Opr\u0161al, J., Pinsker, M.: The wonderland of reflections. Isr. J. Math. 223(1), 363\u2013398 (2018)","journal-title":"Isr. J. Math."},{"key":"3_CR12","unstructured":"Bodirsky, M., Pinsker, M.: Canonical Functions: a Proof via Topological Dynamics (2016). Preprint available under http:\/\/arxiv.org\/abs\/1610.09660"},{"key":"3_CR13","unstructured":"Bodirsky, M., Pinsker, M., Pongr\u00e1cz, A.: Projective clone homomorphisms. Accepted for publication in the Journal of Symbolic Logic (2014). Preprint arXiv:1409.4601"},{"key":"3_CR14","unstructured":"Bulatov, A.A.: Tractable conservative constraint satisfaction problems. In: Proceedings of the Symposium on Logic in Computer Science (LICS), Ottawa, Canada, pp. 321\u2013330 (2003)"},{"key":"3_CR15","unstructured":"Bulatov, A.A.: Conservative constraint satisfaction revisited (2014). Manuscript, ArXiv:1408.3690v1"},{"key":"3_CR16","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":"3_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511623677","volume-title":"Permutation Groups. LMS Student Text 45","author":"PJ Cameron","year":"1999","unstructured":"Cameron, P.J.: Permutation Groups. LMS Student Text 45. Cambridge University Press, Cambridge (1999)"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.artint.2004.02.003","volume":"156","author":"M Cristiani","year":"2004","unstructured":"Cristiani, M., Hirsch, R.: The complexity of the constraint satisfaction problem for small relation algebras. Artif. Intell. J. 156, 177\u2013196 (2004)","journal-title":"Artif. Intell. J."},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s10462-004-5899-8","volume":"23","author":"I D\u00fcntsch","year":"2005","unstructured":"D\u00fcntsch, I.: Relation algebras and their application in temporal and spatial reasoning. Artif. Intell. Rev. 23, 315\u2013357 (2005)","journal-title":"Artif. Intell. Rev."},{"key":"3_CR20","volume-title":"Relation Algebras by Games","author":"R Hirsch","year":"2002","unstructured":"Hirsch, R., Hodkinson, I.: Relation Algebras by Games. North Holland, Amsterdam (2002)"},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(95)00042-9","volume":"83","author":"R Hirsch","year":"1996","unstructured":"Hirsch, R.: Relation algebras of intervals. Artif. Intell. J. 83, 1\u201329 (1996)","journal-title":"Artif. Intell. J."},{"issue":"3","key":"3_CR22","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1093\/logcom\/7.3.309","volume":"7","author":"R Hirsch","year":"1997","unstructured":"Hirsch, R.: Expressive power and complexity in algebraic logic. J. Log. Comput. 7(3), 309\u2013351 (1997)","journal-title":"J. Log. Comput."},{"issue":"4","key":"3_CR23","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1093\/jigpal\/7.4.547","volume":"7","author":"R Hirsch","year":"1999","unstructured":"Hirsch, R.: A finite relation algebra with undecidable network satisfaction problem. Log. J. IGPL 7(4), 547\u2013554 (1999)","journal-title":"Log. J. IGPL"},{"key":"3_CR24","volume-title":"A Shorter Model Theory","author":"W Hodges","year":"1997","unstructured":"Hodges, W.: A Shorter Model Theory. Cambridge University Press, Cambridge (1997)"},{"issue":"3","key":"3_CR25","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1145\/176584.176585","volume":"41","author":"PB Ladkin","year":"1994","unstructured":"Ladkin, P.B., Maddux, R.D.: On binary constraint problems. J. Assoc. Comput. Mach. 41(3), 435\u2013469 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR26","volume-title":"Relation Algebras","author":"RD Maddux","year":"2006","unstructured":"Maddux, R.D.: Relation Algebras. Elsevier, Amsterdam (2006)"},{"issue":"1\u20132","key":"3_CR27","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0004-3702(99)00002-8","volume":"108","author":"J Renz","year":"1999","unstructured":"Renz, J., Nebel, B.: On the complexity of qualitative spatial reasoning: a maximal tractable fragment of the region connection calculus. Artif. Intell. 108(1\u20132), 69\u2013123 (1999)","journal-title":"Artif. Intell."},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-1-4020-5587-4_4","volume-title":"Handbook of Spatial Logics","author":"J Renz","year":"2007","unstructured":"Renz, J., Nebel, B.: Qualitative spatial reasoning using constraint calculi. In: Aiello, M., Pratt-Hartmann, I., van Benthem, J. (eds.) Handbook of Spatial Logics, pp. 161\u2013215. Springer, Berlin (2007). https:\/\/doi.org\/10.1007\/978-1-4020-5587-4_4"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Vilain, M., Kautz, H., van Beek, P.: Constraint propagation algorithms for temporal reasoning: a revised report. In: Reading in Qualitative Reasoning About Physical Systems, pp. 373\u2013381 (1989)","DOI":"10.1016\/B978-1-4832-1447-4.50034-1"},{"key":"3_CR30","doi-asserted-by":"crossref","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)","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["Lecture Notes in Computer Science","Relational and Algebraic Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-43520-2_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T19:02:34Z","timestamp":1709665354000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-43520-2_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030435196","9783030435202"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-43520-2_3","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":"1 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RAMiCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Relational and Algebraic Methods in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Palaiseau","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","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":"26 October 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 October 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ramics2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/ramics18.gforge.inria.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","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":"29","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":"20","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":"0","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":"69% - 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":"4","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":"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 COVID-19 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)"}}]}}