Bodirsky, Manuel; Chen, Hubie; Kára, Jan; von Oertzen, Timo 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]. Cited in 1 Document 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 \textit{M. Bodirsky} et al., Lect. Notes Comput. Sci. 4596, 546--557 (2007; Zbl 1171.68722) Full Text: DOI Link