Show simple item record

dc.contributor.authorCarvalho, Catarina
dc.contributor.authorDalmau, Victor
dc.contributor.authorKrokhin, Andrei
dc.date.accessioned2013-01-14T14:29:03Z
dc.date.available2013-01-14T14:29:03Z
dc.date.issued2011
dc.identifier.citationCarvalho , C , Dalmau , V & Krokhin , A 2011 , ' Two new homomorphism dualities and lattice operations ' , Journal of Logic and Computation , vol. 21 , no. 6 , pp. 1065-1092 . https://doi.org/10.1093/logcom/exq030
dc.identifier.issn1465-363X
dc.identifier.otherPURE: 774997
dc.identifier.otherPURE UUID: 866bd827-2409-4965-9c96-70e7bbb60dd2
dc.identifier.otherScopus: 82455219121
dc.identifier.urihttp://hdl.handle.net/2299/9617
dc.description.abstractThe 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.en
dc.language.isoeng
dc.relation.ispartofJournal of Logic and Computation
dc.titleTwo new homomorphism dualities and lattice operationsen
dc.contributor.institutionSchool of Physics, Astronomy and Mathematics
dc.contributor.institutionScience & Technology Research Institute
dc.contributor.institutionCentre for Computer Science and Informatics Research
dc.description.statusPeer reviewed
dc.relation.schoolSchool of Physics, Astronomy and Mathematics
dcterms.dateAccepted2011
rioxxterms.versionAM
rioxxterms.versionofrecordhttps://doi.org/10.1093/logcom/exq030
rioxxterms.typeJournal Article/Review
herts.preservation.rarelyaccessedtrue


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record