CD(4) has bounded width

Catarina Carvalho; Víctor Dalmau; Petar Marković; Miklós Maróti

doi:10.1007/s00012-009-2113-5

CD(4) has bounded width

Catarina Carvalho
, Víctor Dalmau
, Petar Marković
, Miklós Maróti

Research output: Contribution to journal › Article › peer-review

8 Citations (Scopus)

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.

Original language	English
Pages (from-to)	293-297
Journal	Algebra Universalis
Volume	60
DOIs	https://doi.org/10.1007/s00012-009-2113-5
Publication status	Published - 2009

Keywords

math.LO
cs.CC
68N17 (Primary) 08A70, 08B10, 08B05, 03B70, 68T20 (Secondary)

Access to Document

10.1007/s00012-009-2113-5

Cite this

@article{3fdbd36e4d9e41a2b0661e97adf18764,

title = "CD(4) has bounded width",

abstract = "We prove that the constraint languages invariant under a short sequence of J\textbackslash{}'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.",

keywords = "math.LO, cs.CC, 68N17 (Primary) 08A70, 08B10, 08B05, 03B70, 68T20 (Secondary)",

author = "Catarina Carvalho and V{\'i}ctor Dalmau and Petar Markovi{\'c} and Mikl{\'o}s Mar{\'o}ti",

year = "2009",

doi = "10.1007/s00012-009-2113-5",

language = "English",

volume = "60",

pages = "293--297",

journal = "Algebra Universalis",

issn = "1420-8911",

publisher = "Birkhauser Verlag Basel",

}

TY - JOUR

T1 - CD(4) has bounded width

AU - Carvalho, Catarina

AU - Dalmau, Víctor

AU - Marković, Petar

AU - Maróti, Miklós

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - math.LO

KW - cs.CC

KW - 68N17 (Primary) 08A70, 08B10, 08B05, 03B70, 68T20 (Secondary)

U2 - 10.1007/s00012-009-2113-5

DO - 10.1007/s00012-009-2113-5

M3 - Article

SN - 1420-8911

VL - 60

SP - 293

EP - 297

JO - Algebra Universalis

JF - Algebra Universalis

ER -

CD(4) has bounded width

Abstract

Keywords

Access to Document

Fingerprint

Cite this