05949368

a

05949368 Creed, P\'aid{\'\i} \v{Z}ivn\'y, Stanislav On minimal weighted clones. Lee, Jimmy (ed.), Principles and practice of constraint programming -- CP 2011. 17th international conference, CP 2011, Perugia, Italy, September 12--16, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23785-0/pbk). Lecture Notes in Computer Science 6876, 210-224 (2011). 2011 Berlin: Springer EN

doi:10.1007/978-3-642-23786-7_18

Summary: The connection between the complexity of constraint languages and clone theory, discovered by Cohen and Jeavons in a series of papers, has been a fruitful line of research on the complexity of CSPs. In a recent result, Cohen et al. [14] have established a Galois connection between the complexity of valued constraint languages and so-called weighted clones. In this paper, we initiate the study of weighted clones. Firstly, we prove an analogue of Rosenberg's classification of minimal clones for weighted clones. Secondly, we show minimality of several weighted clones whose support clone is generated by a single minimal operation. Finally, we classify all Boolean weighted clones. This classification implies a complexity classification of Boolean valued constraint languages obtained by Cohen et al. [13]