Back to Search Start Over

CSP for binary conservative relational structures.

Authors :
Kazda, Alexandr
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