Constraint satisfaction with infinite domains [Elektronische Ressource] / von Manuel Bodirsky

Sujets

• Informatik

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2004
• Nombre de lectures: 27
• Langue: Deutsch

Extrait

Constraint Satisfaction with Infinite Domains
Dissertation
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften (doctor rerum naturalium)
im Fach Informatik
eingereicht an der
Mathematisch-Naturwissenschaftlichen Fakultat¨ II
der Humboldt-Universit¨ at zu Berlin
von Dipl.-Inf.
Manuel Bodirsky
geboren am 30. Dezember 1976 in Freiburg im Breisgau
Pr¨ asident der Humboldt-Universit¨ at zu Berlin
Prof. Dr. Jur¨ gen Mlynek
Dekan der Mathematisch-Naturwissenschaftlichen Fakult¨ at II
Prof. Dr. Uwe Ku¨chler
Gutachter:
1. Prof. Dr. Hans Jur¨ gen Pr¨ omel
2. Prof. Dr. Martin Grohe
3. Prof. Jaroslav Neˇsetˇril
Tag der Einreichung: 6.7.2004, Vorsitzender Prof. Dr. Johannes K¨ obler
Tag der mundlic¨ hen Prufung:¨ 4.11.2004Zusammenfassung. Constraint Satisfaction Probleme tauchen in vielen
Gebieten der Informatik auf, insbesondere im Gebiet der kunstlic¨ hen Intel-
ligenz, zum Beispiel beim raumlichen und zeitlichen Schließen, maschinel-¨
¨len Sehen, Scheduling. Ein Uberblick findet sich in [Kumar, 1992, Dechter,
2003]. Andere Gebiete sind Graphentheorie, Aussagenlogik, Typsysteme fur¨
Programmiersprachen, Datenbanktheorie, automatisches Beweisen, Compu-
terlinguistik und Bioinformatik.
Viele Constraint Satisfaction Probleme konnen auf naturliche Weise als¨ ¨
Homomorphieprobleme formuliert werden. Hier betrachten wir fur¨ eine fest-
gehaltene relationale Struktur Γ das folgende Berechnungsproblem: Gegeben
sei eine Struktur S mit der gleichen relationalen Signatur wie Γ, gefragt ist
ob es einen Homomorphismus von S nach Γ gibt. Dieses Problem ist das
Constraint Satisfaction Problem CSP(Γ) fur Γ, und wurde fur endliches Γ –¨ ¨
die sogenannteSchablone des Problems – intensiv untersucht. Allerdings gibt
es viele Constraint Satisfaction Probleme, die nicht mit endlicher Schablone
formuliert werden konnen.¨
Wenn wir beliebige unendliche Schablonen zulassen, wird Constraint Sa-
tisfaction zu einem sehr ausdrucksstarken Formalismus, und wir konnen dann¨
beispielsweise unentscheidbare Probleme als Constraint Satisfaction Proble-
me formulieren. In dieser Arbeit machen wir daher zusatzliche Annahmen fur¨ ¨
die Schablone. Eine dieser Annahmen ist ω-Kategorizit¨at. Eine abzahlba¨ re
Struktur Γ istω-kategorisch, wenn alle abzahlbaren Modelle der erststufigen¨
Theorie von Γ isomorph zu Γ sind. Dies ist ein zentrales Konzept aus der
Modelltheorie und eng verwandt mit Quantor-elimination und Homogenit¨at.
Wir fuhren Argumente an, warum ω-Kategorizitat ein sinnvoller Begriff ist,¨ ¨
wenn man Constraint Satisfaction Probleme mit einer Schablone ub¨ er einem
unendlichen Wertebereich systematisch untersuchen will.
Die Berechnungskomplexitat von Constraint Satisfaction Problemen hangt¨ ¨
im wesentlichen davon ab, welche Relationen der Schablone primitiv positiv
definierbar sind. Furω-kategorische Schablonen konnen wir zeigen, daß eine¨ ¨
Relation in Γ primitiv positiv definierbar ist dann und genau dann, wenn
sie von den Polymorphismen in Γ erhalten wird. Dieser Satz ist fur endliche¨
Strukturen wohlbekannt [Bodnarˇcuk et al., 1969], und war der Ausgangs-
punkt des algebraischen Ansatzes zur Untersuchung der Berechnungskom-
plexitat¨ von Constraint Satisfaction mit endlichen Schablonen – siehe zum
Beispiel [Jeavons et al., 1997]. Wir zeigen an einem Beispiel, daß fur¨ nicht
ω-kategorische Strukturen dieser Satz im allgemeinen nicht gilt.
Eine Konsequenz dieses Satzes ist, daß sowohl fur¨ endliche als auch fur¨
iunendlicheω-kategorische Schablonen die Existenz eines effizienten Algorith-
mus fur das entsprechende Constraint Satisfaction Problem von der Existenz¨
gewisser Polymorphismen der Schablone abhang¨ t. Ein Beispiel sind die ω-
kategorischen Strukturen mit einem k-stelligen fast-einstimmigen Polymor-
phismus. In diesem Fall kann das entsprechende Constraint Satisfaction Pro-
blem in polynomieller Zeit mit Hilfe einesDatalogProgrammes gelost¨ werden.
Datalog ist ein Konzept aus der Datenbanktheorie, und wurde im Zusammen-
hang mit Constraint Satisfaction zum erstenmal in [Feder and Vardi, 1999]
betrachtet. Dort werden fur Constraint Satisfaction Probleme mit endlicher¨
Schablone auch sogenannte kanonische Datalog Programme eingefuhrt,¨ und
es wird gezeigt, daß sich jedes Constraint Satisfaction Problem mit endlicher
Schablone, das mit einem Datalog programm mit k Variablen gel¨ost werden
kann, auch vom sogenanntenkanonischen Datalog Programm mitk Variablen
gel¨ost werden kann. Wir verallgemeinern dies aufω-kategorische Schablonen
gilt.
Die zweite Anforderung, die wir in dieser Arbeit bisweilen an die Scha-
blone stellen, ist, daß Γ durch verbotene induzierte Substrukturen beschrie-
ben werden kann. In diesem Fall ist CSP(Γ) in der Klasse monoton SNP
enthalten, einem Fragment existentieller zweitstufiger Logik, das im Zusam-
menhang mit Constraint Satisfaction in [Feder and Vardi, 1999] betrachtet
wurde. Diese Annahmen fur die Schablone sind allgemein genug, um vie-¨
le zus¨atzliche Constraint Satisfaction Probleme zu erfassen, die nicht mit
endlichen Schablonen formuliert werden konnen. Beispielsweise kann jedes¨
Problem in monoton monadisch SNP – einer anderen Klasse die von Feder
und Vardi eingefuhrt wurde – als Constraint Satisfaction Problem mit einer¨
solchen Schablone formuliert werden.
In den letzten zwei Kapiteln dieser Arbeit beschaftig¨ en wir uns mit kon-
kreten Constraint Satisfaction Problemen mit ω-kategorischer baumartiger
Schablone. Manche dieser Berechnungsprobleme haben Anwendungen in Com-
puterlinguistik [Koller et al., 2000, Niehren and Thater, 2003] und Bioinfor-
matik [Steel, 1992]. Wir geben neuartige Graphalgorithmen an, die diese
Probleme in Polynomialzeit losen,¨ und direkt Losung¨ en fur¨ erfullbar¨ e Cons-
traint Satisfaction Probleme konstruieren. Zentral ist hier der Begriff einer
freien Menge von Knoten im Constraint Graph, mit dessen Hilfe wir durch
wiederholte Zerlegungen des Constraintgraphen in Zusammenhangskompo-
nenten L¨osungen rekursiv konstruieren konnen.¨ Insbsondere l¨osen wir damit
ein Problem, das in [Cornell, 1994] gestellt wurde. Wir erreichen beim Algo-
rithmus fur¨ Cornell’s Problem subquadratische Laufzeit, wenn wir bekannte
dynamische (dekrementelle) Algorithmen fur starken Zusammenhang in ge-¨
iirichteten Graphen verwenden.
Dominanzconstraints wurden in der Computerlinguistik eingefuhrt¨ [Mar-
cus et al., 1983, Backofen et al., 1995] und finden zahlreiche Anwendun-
gen in zum Beispiel unterspezifizierter Semantik [Egg et al., 2001, Copest-
ake et al., 1999, Bos, 1996], unterspezifizierter Diskursanalyse [Gardent and
Webber, 1998], und Syntaxanalyse mit Baumadjunktionsgrammatiken [Ro-
gers and Vijay-Shanker, 1994]. Es handelt sich um eine Formalismus, im
dem Baume¨ mit Hilfe der Eltern-Kind und der Vorfahre-Nachfahre Relati-
on beschrieben werden konnen.¨ Erfullbar¨ keit von Dominanzconstraints ist
NP-vollstandig [Koller et al., 1998]. Allerdings genugt es fur viele Anwen-¨ ¨ ¨
dungen normale Dominanzconstraints zu betrachten, und diese haben einen
polynomiellen Erfullbarkeitstest [Althaus et al., 2003]. Mit einem ahnlichen¨ ¨
algorithmischen Ansatz wie bei unserem Algorithmus fur¨ Cornell’s Problem
konnen wir einen neuen Algorithmus fur normale Dominanzconstraints an-¨ ¨
geben, der direkt eine L¨osung (oder, falls gewunsc¨ ht, alle L¨osungen) eines
normalen Dominanzconstraints generiert. Der Algorithmus ist dabei effizien-
ter als die bisher bekannten Verfahren. Wieder konnen¨ wir subquadratische
Laufzeit erreichen – hier verwenden wir effiziente dekrementelle Algorithmen
fur zweifachen Graphzusammenhang.¨
Schließlich suchen wir nach schwac¨ heren Annahmen als Normalitat¨ , die
immer noch Polynomialzeitalgorithmen zulassen, das heißt, nach großeren¨
handhabbaren Fragmenten von Dominanzconstraints. In diesem Kontext de-
finieren wir die Klasse der surjektiven Homomorphieprobleme. Wie im Falle
von Homomorphieproblemen sind Probleme der Klasse durch eine (in die-
sem Falle immer endliche) Schablone T gegeben, und wir fragen ob es fur¨
eine gegebene endliche Struktur S mit der gleichen Signatur wie T einen
Homomorphismus von S nach T gibt. Wir zeigen, daß bestimmte Fragmen-
te von Dominanzconstraints unter Polynomialzeitreduktionen equivalent zu
surjektiven Homomorphieproblemen sind.
iiiAbstract. Constraint satisfaction problems occur in many areas of com-
puter science, most prominently in artificial intelligence including temporal
or spacial reasoning, belief maintenance, machine vision, and scheduling (for
an overview see [Kumar, 1992,Dechter, 2003]). Other areas are graph theory,
boolean satisfiability, type systems for programming languages, database the-
ory, automatic theorem proving, and, as for some of the problems discussed
in this thesis, computational linguistics and computational biology.
Many constraint satisfaction problems have a natural formulation as a
homomorph