| Autor(en): |
Manuel Bodirsky |
Titel: |
Constraint satisfaction with infinite domains |
| Gutachter: |
Hans Jürgen Prömel; Jaroslav Nesetril; Martin Grohe |
| Erscheinungsdatum: |
06.07.2004 |
| Volltext: |
pdf
(urn:nbn:de:kobv:11-10035566)
|
| Fachgebiet(e): |
Informatik |
| Schlagwörter (ger): |
Constraint Satisfaction, Abzählbar kategorische Strukturen, Datalog, Baumbeschreibungssprachen, Dominanz Constraints, Homomorphie Probleme |
| Schlagwörter (eng): |
Constraint Satisfaction, Countably Categorical Structures, Datalog, Tree Description Languages, Dominance Constraints, Homomorphism Problems |
| Einrichtung: |
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II |
| Zitationshinweis: |
Bodirsky, Manuel:
Constraint satisfaction with infinite domains;
Dissertation,
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 06.07.2004, urn:nbn:de:kobv:11-10035566
|
Metadatenexport:
 Um
den gesamten Metadatensatz im Endnote- oder
Bibtex-Format zu speichern,
klicken Sie bitte auf den entsprechenden Link.
|
Endnote
Bibtex
|
| print on demand:
Wenn
Sie auf dieses Icon klicken, können Sie
ein Druckexemplar dieser Publikation bestellen.
|
|
| Diese Seite taggen:
Diese
Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie
Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer
ansehen können.
|
|
| Abstract (ger): |
| 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.
|
| Abstract (eng): |
| 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. |
Zugriffsstatistik:
Die Daten für die Zugriffsstatistik der einzelnen Dokumente
wurden aus den durch AWStats aggregierten Webserver-Logs erstellt.
Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie
auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen
(insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert
auf eine der Dateien (Kapitel) des Dokuments angezeigt.
Um die detaillierten Zugriffszahlen zu sehen,
fahren Sie bitte mit dem Mauszeiger
über die einzelnen Balken des Diagramms.
|
  | | | | | | | | | | | | | | | | | | | Jun
11 | Jul
11 | Aug
11 | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Apr
13 |
| Monat | Jun
11 | Jul
11 | Aug
11 | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Apr
13 | | Startseite | 2 | 6 | 2 | 4 | 1 | 2 | | | | | 2 | 7 | 2 | | | | | | | | PDF | 2 | 6 | 3 | 2 | 4 | 4 | 6 | 7 | 13 | 13 | 15 | 34 | 20 | 20 | 21 | 29 | 16 | 28 | 36 |
Gesamtzahl der Zugriffe seit Jun 2011: - Startseite – 28 (1.47 pro Monat)
- PDF – 279 (14.68 pro Monat)
|
