Manuel Bodirsky
Maximal Infinite-Valued Constraint Languages
With Hubie Chen, Jan Kára, Timo von Oertzen. Theoretical Computer Science (TCS), 410, pages 1684-1693, 2009. An extended abstract of this paper appeared in the Proceedings of the International Colloquium on Colloquium on Automata, Languages and Programming (ICALP07).
Abstract
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 a countably categorical structure, then maximal constraint languages are in one-to-one correspondence to minimal oligomorphic clones, i.e., locally closed clones whose permutations form an oligormophic permutation group. Based on this correspondence, we derive general tractability and hardness criteria for the corresponding constraint satisfaction problems.
Download
Download: a post-print of the journal version of this paper is available in pdf.
Remarks on Related Papers
Some results in this paper build upon previous work with Hubie Chen about oligomorphic clones. Also see my survey on Constraint Satisfaction Problems with Infinite Templates.
