Carvalho, CatarinaDalmau, VíctorKrokhin, Andrei2019-01-182019-01-182010Carvalho C, Dalmau V, Krokhin A. CSP duality and trees of bounded pathwidth. Theor Comput Sci. 2010 Jul 17;411(34-36):3188-208. DOI: 10.1016/j.tcs.2010.05.0160304-3975http://hdl.handle.net/10230/36329We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algebraic terms. For this, we introduce a new parameter for trees that closely approximates pathwidth and can be characterised via a hypergraph searching game.application/pdfeng© Elsevier http://dx.doi.org/10.1016/j.tcs.2010.05.016info:eu-repo/semantics/articlehttp://dx.doi.org/10.1016/j.tcs.2010.05.016Constraint satisfaction problemHomomorphism dualityDatalogPolymorphismsBounded pathwidthinfo:eu-repo/semantics/openAccess