×

Maximal infinite-valued constraint languages. (English) Zbl 1171.68722

Arge, Lars (ed.) et al., Automata, languages and programming. 34th international colloquium, ICALP 2007, Wrocław, Poland, July 9–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73419-2/pbk). Lecture Notes in Computer Science 4596, 546-557 (2007).
Summary: 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.
For the entire collection see [Zbl 1119.68002].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
03C35 Categoricity and completeness of theories
08A70 Applications of universal algebra in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI Link