dc.contributor.author | Carvalho, Catarina | |
dc.contributor.author | Dalmau, Víctor | |
dc.contributor.author | Marković, Petar | |
dc.contributor.author | Maróti, Miklós | |
dc.date.accessioned | 2013-01-14T14:29:01Z | |
dc.date.available | 2013-01-14T14:29:01Z | |
dc.date.issued | 2009 | |
dc.identifier.citation | Carvalho , C , Dalmau , V , Marković , P & Maróti , M 2009 , ' CD(4) has bounded width ' , Algebra Universalis , vol. 60 , pp. 293-297 . https://doi.org/10.1007/s00012-009-2113-5 | |
dc.identifier.issn | 1420-8911 | |
dc.identifier.other | ArXiv: http://arxiv.org/abs/0709.1934v1 | |
dc.identifier.other | ORCID: /0000-0002-4648-7016/work/62748320 | |
dc.identifier.uri | http://hdl.handle.net/2299/9616 | |
dc.description.abstract | We prove that the constraint languages invariant under a short sequence of J\'onsson terms (containing at most three non-trivial ternary terms) are tractable by showing that they have bounded width. This improves the previous result by Kiss and Valeriote and presents some evidence that the Larose-Zadori conjecture holds in the congruence-distributive case. | en |
dc.format.extent | 571594 | |
dc.language.iso | eng | |
dc.relation.ispartof | Algebra Universalis | |
dc.subject | math.LO | |
dc.subject | cs.CC | |
dc.subject | 68N17 (Primary) 08A70, 08B10, 08B05, 03B70, 68T20 (Secondary) | |
dc.title | CD(4) has bounded width | en |
dc.contributor.institution | Mathematics and Theoretical Physics | |
dc.contributor.institution | Centre for Computer Science and Informatics Research | |
dc.contributor.institution | School of Physics, Engineering & Computer Science | |
dc.contributor.institution | Department of Physics, Astronomy and Mathematics | |
dc.description.status | Peer reviewed | |
rioxxterms.versionofrecord | 10.1007/s00012-009-2113-5 | |
rioxxterms.type | Journal Article/Review | |
herts.preservation.rarelyaccessed | true | |