2026-07-23T18:08:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14207 2024-03-12T12:00:00Z ddc:004 open_access

Smooth Approximations and Relational Width Collapses Mottet, Antoine Nagy, Tomáš Pinsker, Michael Wrona, Michał local consistency bounded width constraint satisfaction problems polymorphisms smooth approximations We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities n ≥ 3) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain CSPs studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of MMSNP sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu et al.. In particular, the bounded width hierarchy collapses in those cases as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Mottet and Tomáš Nagy and Michael Pinsker and Michał Wrona 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.138 urn:nbn:de:0030-drops-142075 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.138 eng https://creativecommons.org/licenses/by/4.0/legalcode