Zur Kurzanzeige

2004-07-06Dissertation DOI: 10.18452/15173
Constraint satisfaction with infinite domains
dc.contributor.authorBodirsky, Manuel
dc.date.accessioned2017-06-18T06:30:16Z
dc.date.available2017-06-18T06:30:16Z
dc.date.created2005-01-31
dc.date.issued2004-07-06
dc.identifier.urihttp://edoc.hu-berlin.de/18452/15825
dc.description.abstractConstraint 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.ger
dc.description.abstractConstraint 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.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectConstraint Satisfactionger
dc.subjectAbzählbar kategorische Strukturenger
dc.subjectDatalogger
dc.subjectBaumbeschreibungssprachenger
dc.subjectDominanz Constraintsger
dc.subjectHomomorphie Problemeger
dc.subjectConstraint Satisfactioneng
dc.subjectCountably Categorical Structureseng
dc.subjectDatalogeng
dc.subjectTree Description Languageseng
dc.subjectDominance Constraintseng
dc.subjectHomomorphism Problemseng
dc.subject.ddc004 Informatik
dc.titleConstraint satisfaction with infinite domains
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-10035566
dc.identifier.doihttp://dx.doi.org/10.18452/15173
dc.identifier.alephidHU001160623
dc.date.accepted2004-11-04
dc.contributor.refereePrömel, Hans Jürgen
dc.contributor.refereeNesetril, Jaroslav
dc.contributor.refereeGrohe, Martin
dc.subject.dnb28 Informatik, Datenverarbeitung
local.edoc.type-nameDissertation
bua.departmentMathematisch-Naturwissenschaftliche Fakultät II

Zur Kurzanzeige