{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T04:08:27Z","timestamp":1770955707352,"version":"3.50.1"},"reference-count":43,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"name":"European Research Council","award":["101071674"],"award-info":[{"award-number":["101071674"]}]},{"name":"DFG","award":["467967530"],"award-info":[{"award-number":["467967530"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>In this paper, we show that the problem of deciding for a given finite relation algebra [Formula: see text] whether the network satisfaction problem for [Formula: see text] can be solved by the k-consistency procedure, for some [Formula: see text], is undecidable. For the important class of finite relation algebras [Formula: see text] with a normal representation, however, the decidability of this problem remains open. We show that if [Formula: see text] is symmetric and has a flexible atom, then the question whether [Formula: see text] can be solved by k-consistency, for some [Formula: see text], is decidable (even in polynomial time in the number of atoms of [Formula: see text]). This result follows from a more general sufficient condition for the correctness of the k-consistency procedure for finite symmetric relation algebras. In our proof we make use of a result of Alexandr Kazda about finite binary conservative structures.<\/jats:p>","DOI":"10.1142\/s0218196726500013","type":"journal-article","created":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T03:58:21Z","timestamp":1760673501000},"page":"121-152","source":"Crossref","is-referenced-by-count":0,"title":["Network satisfaction problems solved by\n                    <i>k<\/i>\n                    -consistency"],"prefix":"10.1142","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8228-3611","authenticated-orcid":false,"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Algebra, TU Dresden, 01062 Dresden, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-7421-8565","authenticated-orcid":false,"given":"Simon","family":"Kn\u00e4uer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Algebra, TU Dresden, 01062 Dresden, Germany"}]}],"member":"219","published-online":{"date-parts":[[2025,12,18]]},"reference":[{"key":"S0218196726500013BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_26"},{"key":"S0218196726500013BIB002","doi-asserted-by":"publisher","DOI":"10.37236\/773"},{"key":"S0218196726500013BIB003","doi-asserted-by":"crossref","unstructured":"L. Barto, The dichotomy for conservative constraint satisfaction problems revisited, in\n                      Proc. Symp. Logic in Computer Science (LICS)\n                      (IEEE, 2011), pp. 301\u2013310, A preliminary version appeared in the proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201905).","DOI":"10.1109\/LICS.2011.25"},{"key":"S0218196726500013BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.05.012"},{"key":"S0218196726500013BIB005","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5260"},{"key":"S0218196726500013BIB006","unstructured":"M. Bodirsky, M. Jahn, M. Konecn\u00fd, S. Kn\u00e4uer and P. Winkler, The network satisfaction problem for relation algebras with at most 4 atoms, preprint (2025), arXiv:2507.09324."},{"key":"S0218196726500013BIB007","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"S0218196726500013BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-43520-2_3"},{"key":"S0218196726500013BIB009","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i7.16773"},{"key":"S0218196726500013BIB010","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.14195"},{"key":"S0218196726500013BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070906"},{"issue":"2","key":"S0218196726500013BIB012","first-page":"1","volume":"14","author":"Bodirsky M.","year":"2018","journal-title":"Log. Methods Comput. Sci."},{"key":"S0218196726500013BIB013","unstructured":"M. Bodirsky, Complexity classification in infinite-domain constraint satisfaction, M\u00e9moire d\u2019habilitation \u00e0 diriger des recherches, Universit\u00e9 Diderot \u2013 Paris 7, preprint (2012), arXiv:1201.0856v8."},{"key":"S0218196726500013BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02149-8_1"},{"key":"S0218196726500013BIB015","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2003.1210072"},{"key":"S0218196726500013BIB016","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"S0218196726500013BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.07.004"},{"key":"S0218196726500013BIB018","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"S0218196726500013BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.02.003"},{"key":"S0218196726500013BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/3134757"},{"key":"S0218196726500013BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-004-5899-8"},{"key":"S0218196726500013BIB022","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"S0218196726500013BIB023","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"issue":"4","key":"S0218196726500013BIB024","first-page":"1387","volume":"353","author":"Hirsch R.","year":"2001","journal-title":"Trans. Amer. Math. Soc."},{"issue":"6","key":"S0218196726500013BIB025","first-page":"1819","volume":"130","author":"Hirsch R.","year":"2001","journal-title":"Trans. Amer. Math. Soc."},{"key":"S0218196726500013BIB026","volume-title":"Relation Algebras by Games","author":"Hirsch R.","year":"2002"},{"key":"S0218196726500013BIB027","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00042-9"},{"key":"S0218196726500013BIB028","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/7.3.309"},{"key":"S0218196726500013BIB029","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/7.4.547"},{"key":"S0218196726500013BIB030","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.02.033"},{"key":"S0218196726500013BIB031","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-015-0358-8"},{"key":"S0218196726500013BIB032","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-015-0327-2"},{"key":"S0218196726500013BIB033","unstructured":"S. Kn\u00e4uer,\n                      Constraint Network Satisfaction for Finite Relation Algebras\n                      , Ph.D. thesis, Technische Universit\u00e4t Dresden (2023)."},{"key":"S0218196726500013BIB034","doi-asserted-by":"publisher","DOI":"10.2307\/1969375"},{"key":"S0218196726500013BIB035","doi-asserted-by":"publisher","DOI":"10.1007\/BF01221799"},{"key":"S0218196726500013BIB036","volume-title":"Relation Algebras","volume":"150","author":"Maddux R. D.","year":"2006"},{"key":"S0218196726500013BIB037","unstructured":"R. McKenzie,\n                      The Representation of Relation Algebras\n                      , Ph.D. thesis, University of Colorado at Boulder (1966)."},{"key":"S0218196726500013BIB038","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1029000477"},{"key":"S0218196726500013BIB039","first-page":"138:1","volume-title":"48th Int. Colloq. Automata, Languages, and Programming, ICALP","author":"Mottet A.","year":"2021"},{"key":"S0218196726500013BIB040","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-5587-4_4"},{"issue":"80","key":"S0218196726500013BIB041","volume":"54","author":"Tarski A.","year":"1948","journal-title":"Bull. Amer. Math. Soc."},{"key":"S0218196726500013BIB042","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"},{"key":"S0218196726500013BIB043","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196726500013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T03:42:18Z","timestamp":1770954138000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196726500013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,18]]},"references-count":43,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1142\/S0218196726500013"],"URL":"https:\/\/doi.org\/10.1142\/s0218196726500013","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,18]]}}}