Two new homomorphism dualities and lattice operations
Carvalho, Catarina, Dalmau, Victor and Krokhin, Andrei
(2011)
Two new homomorphism dualities and lattice operations.
Journal of Logic and Computation, 21 (6).
pp. 1065-1092.
ISSN 1465-363X
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.
Item Type | Article |
---|---|
Identification Number | 10.1093/logcom/exq030 |
Date Deposited | 15 May 2025 12:25 |
Last Modified | 10 Sep 2025 20:38 |
Full text not available from this repository.
Downloads
?
Total file downloads from UHRA since January 2020. For more information on metrics see the IRUS guide.