Wiehe, AntoineAntoineWieheNagy, TomášTomášNagyPinsker, MichaelMichaelPinskerWrona, MichałMichałWrona2025-01-032025-01-032024-12-11SIAM Journal on Computing 53 (6): 1709-1745 (2024-12-11)https://tore.tuhh.de/handle/11420/52824We 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 constraint satisfaction problems (CSPs) studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of Monotone Monadic SNP (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. Our results extend the scope of theorems of Barto and Kozik characterizing bounded width for finite structures and show the applicability of infinite-domain CSPs to other fields.en0097-539720246Society for Industrial & Applied Mathematics (SIAM)Journal Article10.1137/22m1538934Journal Article