Showing cs.LOShow all
3 papers · 1 filter
cs.LO2025
An order out of nowhere: a new algorithm for infinite-domain CSPs
Antoine Mottet, Tomáš Nagy, Michael Pinsker
We consider the problem of satisfiability of sets of constraints in a given set of finite uniform hypergraphs. While the problem under consideration is similar in nature to the pro…
cs.LO2024
Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough
Antoine Mottet, Tomáš Nagy, Michael Pinsker +1
We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities ) have low relational width. This implies a c…
cs.LO2024
Strict width for Constraint Satisfaction Problems over homogeneous strucures of finite duality
Tomáš Nagy, Michael Pinsker
We investigate the `local consistency implies global consistency' principle of strict width among structures within the scope of the Bodirsky-Pinsker dichotomy conjecture for infin…