Two new homomorphism dualities and lattice operations

Catarina Carvalho, Victor Dalmau, Andrei Krokhin

    Research output: Contribution to journalArticlepeer-review

    6 Citations (Scopus)


    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 recursive fragment of Datalog - monadic linear Datalog with at most one EDB per rule, and also in the smallest non-linear extension of this fragment. We give combinatorial and algebraic characterisations of such problems, in terms of homomorphism dualities and lattice operations, respectively. We then apply our results to study graph H-colouring problems.
    Original languageEnglish
    Pages (from-to)1065-1092
    JournalJournal of Logic and Computation
    Volume 21
    Issue number6
    Publication statusPublished - 2011


    Dive into the research topics of 'Two new homomorphism dualities and lattice operations'. Together they form a unique fingerprint.

    Cite this