{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:03Z","timestamp":1753889703208,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2007,6,8]],"date-time":"2007-06-08T00:00:00Z","timestamp":1181260800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Constraint languages that arise from finite algebras have recently been the\nobject of study, especially in connection with the Dichotomy Conjecture of\nFeder and Vardi. An important class of algebras are those that generate\ncongruence distributive varieties and included among this class are lattices,\nand more generally, those algebras that have near-unanimity term operations. An\nalgebra will generate a congruence distributive variety if and only if it has a\nsequence of ternary term operations, called Jonsson terms, that satisfy certain\nequations.\n  We prove that constraint languages consisting of relations that are invariant\nunder a short sequence of Jonsson terms are tractable by showing that such\nlanguages have bounded relational width.<\/jats:p>","DOI":"10.2168\/lmcs-3(2:6)2007","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T12:01:39Z","timestamp":1212494499000},"source":"Crossref","is-referenced-by-count":9,"title":["On tractability and congruence distributivity"],"prefix":"10.46298","volume":"Volume 3, Issue 2","author":[{"given":"Emil","family":"Kiss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Valeriote","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2007,6,8]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1005\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1005\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:00:58Z","timestamp":1681243258000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-3(2:6)2007","relation":{"is-same-as":[{"id-type":"arxiv","id":"0705.2229","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.0705.2229","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"doi","id":"10.1007\/978-3-540-92800-3_5","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2007,6,8]]},"article-number":"1005"}}