• search hit 24 of 28
Back to Result List

Constraint Satisfaction with Infinite Domains

Please always quote using this URN:urn:nbn:de:0296-matheon-2852
  • Many constraint satisfaction problems have a natural formulation as a homomorphism problem. For a fixed relational structure Gamma we consider the following computational problem: Given a structure S with the same relational signature as Gamma, is there a homomorphism from S to Gamma? This problem is known as the constraint satisfaction problem CSP(Gamma) for the so-called template Gamma and is intensively studied for relational structures Gamma with a finite domain. However, many constraint satisfaction problems can not be formulated with a finite template. If we allow arbitrary infinite templates, constraint satisfaction is very expressive. We show that it contains undecidable problems, even if the constraint language is binary. In general, a computational problem can be described as the constraint satisfaction problem of an infinite template if and only if it is closed under inverse homomorphisms and disjoint unions. It is also easy to see that we can restrict our attention to countable templates. In this thesis we study the computational complexity of constraint satisfaction with templates that are omega-categorical. A structure Gamma is omega-categorical if all countable models of the first-order theory of Gamma are isomorphic to Gamma. This concept is central and well-studied in model-theory. On the one hand, omega-categoricity is a rather strong model-theoretic assumption on a relational structure, and we can use them to show that many techniques for constraint satisfaction with finite templates extend to omega-categorical templates.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Manuel Bodirsky
URN:urn:nbn:de:0296-matheon-2852
Referee:Hans Jürgen Prömel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2005/05/11
Release Date:2005/10/31
Institute:Humboldt-Universität zu Berlin
Preprint Number:272
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.