Maximal infinite-valued constraint languages
We systematically investigate the computational complexity of constraint satisfaction problems for constraint languages over an infinite domain. In particular, we study a generalization of the well-established notion of maximal constraint languages from finite to infinite domains. If the constraint language can be defined with an omega-categorical structure, then maximal constraint languages are in one-to-one correspondence to minimal oligomorphic clones. Based on this correspondence, we derive general tractability and hardness criteria for the corresponding constraint satisfaction problems. (c) 2008 Elsevier B.V. All rights reserved.
computational complexity constraint satisfaction universal algebra in computer science countably categorical structures