{"authors":[{"id":"orcid_______::c9cb7a797eb4eee65578edbff6371d0d","fullName":"Manuel Bodirsky","name":"Manuel","surname":"Bodirsky","rank":1,"pid":{"id":{"scheme":"orcid","value":"0000-0001-8228-3611"},"provenance":null}},{"id":null,"fullName":"Simon Knäuer","name":"Simon","surname":"Knäuer","rank":2,"pid":{"id":{"scheme":"orcid_pending","value":"0009-0006-7421-8565"},"provenance":null}}],"openAccessColor":null,"publiclyFunded":false,"eoscIfGuidelines":null,"type":"publication","language":{"code":"eng","label":"English"},"countries":[{"code":"DE","label":"Germany","provenance":null}],"subjects":[{"subject":{"scheme":"keyword","value":"FOS: Computer and information sciences"},"provenance":null},{"subject":{"scheme":"keyword","value":"Datalog"},"provenance":null},{"subject":{"scheme":"keyword","value":"Computational Complexity"},"provenance":null},{"subject":{"scheme":"keyword","value":"Rings and Algebras"},"provenance":null},{"subject":{"scheme":"keyword","value":"Logic"},"provenance":null},{"subject":{"scheme":"keyword","value":"Logic in Computer Science"},"provenance":null},{"subject":{"scheme":"keyword","value":"Relation Algebras"},"provenance":null},{"subject":{"scheme":"FOS","value":"0102 computer and information sciences"},"provenance":null},{"subject":{"scheme":"keyword","value":"Computational Complexity (cs.CC)"},"provenance":null},{"subject":{"scheme":"FOS","value":"01 natural sciences"},"provenance":null},{"subject":{"scheme":"keyword","value":"004"},"provenance":null},{"subject":{"scheme":"keyword","value":"510"},"provenance":null},{"subject":{"scheme":"keyword","value":"Network Satisfaction"},"provenance":null},{"subject":{"scheme":"keyword","value":"Logic in Computer Science (cs.LO)"},"provenance":null},{"subject":{"scheme":"keyword","value":"Rings and Algebras (math.RA)"},"provenance":null},{"subject":{"scheme":"keyword","value":"k-Consistency"},"provenance":null},{"subject":{"scheme":"keyword","value":"FOS: Mathematics"},"provenance":null},{"subject":{"scheme":"keyword","value":"Qualitative Reasoning"},"provenance":null},{"subject":{"scheme":"keyword","value":"Logic (math.LO)"},"provenance":null},{"subject":{"scheme":"keyword","value":"Constraint Satisfaction"},"provenance":null}],"mainTitle":"Network satisfaction problems solved by                     <i>k</i>                     -consistency","subTitle":null,"descriptions":["<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>"],"publicationDate":"2025-12-18","publisher":"World Scientific Pub Co Pte Ltd","embargoEndDate":"2023-04-01","sources":["Crossref"],"formats":["application/pdf"],"contributors":["Manuel Bodirsky and Simon Knäuer"],"coverages":null,"bestAccessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/"},"container":{"name":"International Journal of Algebra and Computation","issnPrinted":"0218-1967","issnOnline":"1793-6500","issnLinking":null,"ep":"152","iss":null,"sp":"121","vol":"36","edition":null,"conferencePlace":null,"conferenceDate":null},"documentationUrls":null,"codeRepositoryUrl":null,"programmingLanguage":null,"contactPeople":null,"contactGroups":null,"tools":null,"size":null,"version":null,"geoLocations":null,"id":"doi_dedup___::22e64d37a071d5c9fa5510bbb5a822e3","originalIds":["10.1142/S0218196726500013","10.1142/s0218196726500013","50|doiboost____|617f4b545fbc4b7a53bcabc3efef4dea","50|datacite____::22e64d37a071d5c9fa5510bbb5a822e3","10.48550/arxiv.2304.12871","50|od________18::15675c2c0848a418374add92cb04ec1d","oai:arXiv.org:2304.12871","50|dblp________::86f856e0fc39c681df99a8851796e42d","50|dblp________::99e9efd5a52f6ac45b70fda53f915454","50|dblp________::ce80363e85d48b8ae25e748b8d929102","50|od______1814::0ab480f0ba7824f0f49c931ae4aad5f3","oai:drops-oai.dagstuhl.de:18168","50|base_oa_____::a74b15477dc58fd6b3c58bc9a8713580","ftdagstuhl:oai:drops-oai.dagstuhl.de:18168"],"pids":[{"scheme":"doi","value":"10.1142/s0218196726500013"},{"scheme":"doi","value":"10.48550/arxiv.2304.12871"},{"scheme":"arXiv","value":"2304.12871"}],"dateOfCollection":null,"lastUpdateTimeStamp":null,"indicators":{"citationImpact":{"citationCount":0.0,"influence":2.2251732E-9,"popularity":2.342466E-9,"impulse":0.0,"citationClass":"C5","influenceClass":"C5","impulseClass":"C5","popularityClass":"C5"}},"projects":[{"id":"corda__h2020::da6a74e1290df94adbbd9e6b97781e12","code":"681988","acronym":"CSP-Infinity","title":"Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones","funder":"European Commission","pids":[{"scheme":"doi","value":"10.3030/681988"}]},{"id":"corda_____he::5fb890e4c5cde8171d1ec77bf9b5a2cf","code":"101071674","acronym":"POCOCOP","title":"Polynomial-time Computation: Opening the Blackboxes in Constraint Problems","funder":"European Commission","pids":[{"scheme":"doi","value":"10.3030/101071674"}]}],"organizations":[{"legalName":"TU Dresden","acronym":"TUD","id":"openorgs____::a6340e6ecf60f6bba163659df985b0f2","pids":[{"scheme":"fundref","value":"501100007491"},{"scheme":"RRID","value":"RRID:nlx_53167"},{"scheme":"ISNI","value":"0000000121117257"},{"scheme":"FundRef","value":"501100023321"},{"scheme":"fundref","value":"501100020132"},{"scheme":"RRID","value":"RRID:SCR_004799"},{"scheme":"Wikidata","value":"Q158158"},{"scheme":"OrgReg","value":"DE0094"},{"scheme":"GRID","value":"grid.4488.0"},{"scheme":"ROR","value":"https://ror.org/042aqky30"},{"scheme":"fundref","value":"501100002957"},{"scheme":"FundRef","value":"501100002957"},{"scheme":"Wikidata","value":"Q31837129"},{"scheme":"FundRef","value":"501100007491"},{"scheme":"FundRef","value":"501100020132"},{"scheme":"OrgRef","value":"827048"},{"scheme":"PIC","value":"983820270"},{"scheme":"fundref","value":"501100023321"},{"scheme":"wikidata","value":"Q31837129"},{"scheme":"PIC","value":"999897729"},{"scheme":"wikidata","value":"Q158158"}]},{"legalName":"Schloss Dagstuhl – Leibniz Center for Informatics","acronym":"IBFI","id":"openorgs____::98c791d123e9b6f3e3eadbb4ae60e529","pids":[{"scheme":"wikidata","value":"Q879857"},{"scheme":"OrgReg","value":"DE1207"},{"scheme":"GRID","value":"grid.469874.0"},{"scheme":"PIC","value":"889869368"},{"scheme":"Wikidata","value":"Q879857"},{"scheme":"ROR","value":"https://ror.org/00k4h2615"},{"scheme":"mag_id","value":"2799853480"},{"scheme":"ISNI","value":"0000000100093196"}]},{"legalName":"TU Dresden","acronym":"TU Dresden","id":"pending_org_::15c6bb6ef83073fdfaf386f58a63107e","pids":null},{"legalName":"Leibniz Association","acronym":"LG","id":"openorgs____::f19bd4f95b81943353a480436ef88fd0","pids":[{"scheme":"GRID","value":"grid.413453.4"},{"scheme":"OrgReg","value":"DE1086"},{"scheme":"Wikidata","value":"Q680090"},{"scheme":"fundref","value":"501100001664"},{"scheme":"ROR","value":"https://ror.org/01n6r0e97"},{"scheme":"ISNI","value":"0000000122243060"},{"scheme":"OrgRef","value":"2443230"},{"scheme":"wikidata","value":"Q680090"},{"scheme":"FundRef","value":"501100001664"},{"scheme":"mag_id","value":"315704651"}]},{"legalName":"TU Dresden","acronym":"TU Dresden","id":"pending_org_::616749030c8042a5bdadd9d764d31d2d","pids":null},{"legalName":"Technical University Dresden, Dresden Germany","acronym":"Technical University Dresden, Dresden Germany","id":"pending_org_::1eed9f20151d8025b585f002652e8792","pids":[{"scheme":"RRID","value":"RRID:SCR_004799"},{"scheme":"ROR","value":"https://ror.org/042aqky30"}]}],"communities":[{"code":"eutopia","label":"EUTOPIA Open Research Portal","provenance":null}],"collectedFrom":[{"key":"openaire____::9e3be59865b2c1c335d32dae2fe7b254","value":"Datacite"},{"key":"openaire____::df45502607927471ecf8a6ae83683ff5","value":"Bielefeld Academic Search Engine (BASE)"},{"key":"opendoar____::155fa09596c7e18e50b58eb7e0c6ccb4","value":"Dagstuhl Research Online Publication Server"},{"key":"openaire____::081b82f96300b6a6e3d282bad31cb6e2","value":"Crossref"},{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},{"key":"opendoar____::6f4922f45568161a8cdf4ad2299f6d23","value":"arXiv.org e-Print Archive"}],"instances":[{"pids":[{"scheme":"doi","value":"10.1142/s0218196726500013"}],"type":"Article","urls":["https://doi.org/10.1142/s0218196726500013"],"publicationDate":"2025-12-18","refereed":"peerReviewed","hostedBy":{"key":"issn___print::0884884b75430a6dac826a40a5bdd2bb","value":"International Journal of Algebra and Computation"},"collectedFrom":{"key":"openaire____::081b82f96300b6a6e3d282bad31cb6e2","value":"Crossref"}},{"pids":[{"scheme":"doi","value":"10.48550/arxiv.2304.12871"}],"license":"CC BY SA","type":"Article","urls":["https://dx.doi.org/10.48550/arxiv.2304.12871"],"publicationDate":"2023-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::55045bd2a65019fd8e6741a755395c8c","value":"Unknown Repository"},"collectedFrom":{"key":"openaire____::9e3be59865b2c1c335d32dae2fe7b254","value":"Datacite"}},{"pids":[{"scheme":"arXiv","value":"2304.12871"}],"accessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/","openAccessRoute":null},"type":"Preprint","urls":["http://arxiv.org/abs/2304.12871"],"publicationDate":"2023-04-25","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::6f4922f45568161a8cdf4ad2299f6d23","value":"arXiv.org e-Print Archive"},"collectedFrom":{"key":"opendoar____::6f4922f45568161a8cdf4ad2299f6d23","value":"arXiv.org e-Print Archive"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.48550/arxiv.2304.12871"}],"type":"Preprint","urls":["https://doi.org/10.48550/arXiv.2304.12871"],"publicationDate":"2023-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},"collectedFrom":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.4230/lipics.icalp.2023.116"}],"type":"Conference object","urls":["https://doi.org/10.4230/LIPIcs.ICALP.2023.116"],"refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},"collectedFrom":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.1142/s0218196726500013"}],"type":"Article","urls":["https://doi.org/10.1142/S0218196726500013"],"publicationDate":"2026-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},"collectedFrom":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.4230/lipics.icalp.2023.116"}],"license":"CC BY","type":"Conference object","urls":["https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.116"],"publicationDate":"2023-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::155fa09596c7e18e50b58eb7e0c6ccb4","value":"Dagstuhl Research Online Publication Server"},"collectedFrom":{"key":"opendoar____::155fa09596c7e18e50b58eb7e0c6ccb4","value":"Dagstuhl Research Online Publication Server"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.4230/lipics.icalp.2023.116"}],"license":"CC BY","accessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/","openAccessRoute":null},"type":"Article","urls":["https://doi.org/https://doi.org/10.4230/LIPIcs.ICALP.2023.116"],"publicationDate":"2023-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::155fa09596c7e18e50b58eb7e0c6ccb4","value":"DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics )"},"collectedFrom":{"key":"openaire____::df45502607927471ecf8a6ae83683ff5","value":"Bielefeld Academic Search Engine (BASE)"}}],"links":[{"header":{"relationType":"resultProject","relationClass":"isProducedBy","relatedIdentifier":"corda__h2020::da6a74e1290df94adbbd9e6b97781e12","relatedRecordType":"project","relationProvenance":"iis","trust":"0.897"},"collectedfrom":[{"dsId":"openaire____::a55eb91348674d853191f4f4fd73d078","dsName":"CORDA - COmmon Research DAta Warehouse - Horizon 2020"}],"projectTitle":"Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones","code":"681988","funding":{"funder":{"id":"ec__________::EC","shortname":"EC","name":"European Commission","jurisdiction":{"code":"EU","label":"European Union"},"pid":null},"level0":{"id":"ec__________::EC::H2020","description":"Horizon 2020 Framework Programme","name":"H2020"},"level1":{"id":"ec__________::EC::H2020::ERC","description":"European Research Council","name":"ERC"},"level2":{"id":"ec__________::EC::H2020::ERC::ERC-COG","description":"Consolidator Grant","name":"ERC-COG"}},"startDate":"2016-10-01","endDate":"2021-09-30"},{"header":{"relationType":"resultProject","relationClass":"isProducedBy","relatedIdentifier":"corda_____he::5fb890e4c5cde8171d1ec77bf9b5a2cf","relatedRecordType":"project","relationProvenance":"iis","trust":"0.897"},"collectedfrom":[{"dsId":"openaire____::3f264f93cf3b0cfc4ede188a6300455c","dsName":"CORDA - COmmon Research DAta Warehouse - Horizon Europe"}],"projectTitle":"Polynomial-time Computation: Opening the Blackboxes in Constraint Problems","code":"101071674","funding":{"funder":{"id":"ec__________::EC","shortname":"EC","name":"European Commission","jurisdiction":{"code":"EU","label":"European Union"},"pid":null},"level0":{"id":"ec__________::EC::HE","description":"Horizon Europe Framework Programme","name":"HE"},"level1":{"id":"ec__________::EC::HE::ERC","description":"European Research Council","name":"ERC"},"level2":{"id":"ec__________::EC::HE::ERC::HORIZON-ERC-SYG","description":"HORIZON ERC Synergy Grants","name":"HORIZON-ERC-SYG"}},"startDate":"2023-03-01","endDate":"2029-02-28"}],"otherTitles":null,"inDiamondJournal":false,"green":true,"isGreen":true,"isInDiamondJournal":false}