Browsing by Author "Krokhin, Andrei"

Now showing items 1-4 of 4

    • Caterpillar duality for constraint satisfaction problems 

      Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei (IEEE, 2008)

    • CSP duality and trees of bounded pathwidth 

      Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei (2010)
      We 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 ...

    • On Algebras with many symmetric operations 

      Carvalho, Catarina; Krokhin, Andrei (2016-08-01)
      We show that, for each finite algebra A, either it has symmetric term operations of all arities or else some finite algebra in the variety generated by A has two automorphisms without a common fixed point. We also show ...

    • Two new homomorphism dualities and lattice operations 

      Carvalho, Catarina; Dalmau, Victor; Krokhin, Andrei (2011)
      The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural ...