Back to Search
Start Over
CSP for binary conservative relational structures.
- Source :
-
Algebra Universalis . Feb2016, Vol. 75 Issue 1, p75-84. 10p. - Publication Year :
- 2016
-
Abstract
- We prove that whenever $${\mathbb {A}}$$ is a 3-conservative relational structure with only binary and unary relations, then the algebra of polymorphisms of $${\mathbb {A}}$$ either has no Taylor operation (i.e., CSP( $${\mathbb {A}}$$ ) is NP-complete), or it generates an SD( $${\wedge}$$ ) variety (i.e., CSP( $${\mathbb {A}}$$ ) has bounded width). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00025240
- Volume :
- 75
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Algebra Universalis
- Publication Type :
- Academic Journal
- Accession number :
- 112358878
- Full Text :
- https://doi.org/10.1007/s00012-015-0358-8