Constraint satisfaction with infinite domains
Mathematisch-Naturwissenschaftliche Fakultät II
Constraint Satisfaction Probleme tauchen in vielen Gebieten der theoretischen Informatik auf. Häufig lassen sie sich auf natürliche Weise als Homomorphieprobleme für eine festgelassene Struktur Gamma formulieren: Die Berechnungsaufgabe besteht dann darin, für eine gegebene Struktur S mit der gleichen relationalen Signatur wie Gamma festzustellen, ob es einen Homomorphismus von S nach Gamma gibt. Dieses Problem wurde für enliche Strukturen Gamma intensiv untersucht. Viele der Constraint Satisfaction Probleme, die in der Literatur betrachtet werden, lassen sich jedoch nicht mit endlichen Schablonen Gamma formulieren. Diese Arbeit verallgemeinert Techniken zur Untersuchung der Berechnungskomplexität von Constraint Satisfaction Problemen mit endlichen Schablonen auf unendliche Schablonen. Insbesondere betrachten wir abzählbar kategorische Schablonen, die von zentraler Bedeutung in Modelltheorie sind. Constraint satisfaction problems occur in many areas of computer science. Often they have a natural formulation as a homomorphism problem for a fixed relational structure Gamma: 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 template Gamma and is intensively studied for relational structures Gamma with a finite domain. However, many constraint satisfaction problems in the literature can not be formulated with a finite template. This thesis generalizes techniques to determine the complexity of constraint satisfaction with finite templates to constraint satisfaction with templates over an infinite domain. In particular, we study templates that are countably categorical. Such structures are a central and well-studied concept in model-theory.
Dateien zu dieser Publikation
Verwandte Publikationen
Anzeige der Publikationen mit ähnlichem Titel, Autor, Urheber und Thema.
-
2003-06-18BuchOptimality and duality theory for stochastic optimization problems with nonlinear dominance constraints Dentcheva, Darinka; Ruszczynski, AndrzejWe consider a new class of optimization problems involving stochastic dominance constraints of second order. We develop a new splitting approach to these models, optimality conditions and duality theory. These results are ...
-
2009-12-03DissertationConstraint based world modeling for multi agent systems in dynamic environments Göhring, DanielDie mobile Robotik stellt ein sehr junges und komplexes Forschungsfelder unserer Zeit dar. Innerhalb der letzten Jahrzehnte wurde es Robotern möglich, sich innerhalb ihrer Umgebung zu bewegen, zu navigieren und mit ihrer ...
-
2009-04-05BuchA model for dynamic chance constraints in hydro power reservoir management Andrieu, L.; Henrion, R.; Römisch, W.In this paper, a model for (joint) dynamic chance constraints is proposed and applied to an optimization problem in water reservoir management. The model relies on discretization of the decision variables but keeps the ...