edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Bastian Laubner
Titel: The structure of graphs and new logics for the characterization of Polynomial Time
Gutachter: Martin Grohe; Erich Grädel; Anuj Dawar
Erscheinungsdatum: 14.06.2011
Volltext: pdf (urn:nbn:de:kobv:11-100188664)
Fachgebiet(e): Informatik
Schlagwörter (ger): endliche Modelltheorie, deskriptive Komplexitätstheorie, Logik für PTIME, Ranglogiken, Normalformen, Intervallgraphen, Choiceless Polynomial Time, Fixpunktlogik
Schlagwörter (eng): finite model theory, descriptive complexity theory, logic for PTIME, rank logics, canonical forms, interval graphs, Choiceless Polynomial Time, fixed-point logic
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Lizenz: Namensnennung (CC BY)
Zitationshinweis: Laubner, Bastian: The structure of graphs and new logics for the characterization of Polynomial Time; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 14.06.2011, urn:nbn:de:kobv:11-100188664
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.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Diese Arbeit leistet Beiträge zu drei Gebieten der deskriptiven Komplexitätstheorie. Zunächst adaptieren wir einen repräsentationsinvarianten Graphkanonisierungsalgorithmus mit einfach exponentieller Laufzeit von Corneil und Goldberg (1984) und folgern, dass die Logik "Choiceless Polynomial Time with Counting" auf Strukturen, deren Relationen höchstens Stelligkeit 2 haben, gerade die Polynomialzeit-Eigenschaften (PTIME) von Fragmenten logarithmischer Größe charakterisiert. Der zweite Beitrag untersucht die deskriptive Komplexität von PTIME-Berechnungen auf eingeschränkten Graphklassen. Wir stellen eine neuartige Normalform von Intervallgraphen vor, die sich in Fixpunktlogik mit Zählen (FP+C) definieren lässt, was bedeutet, dass FP+C auf dieser Graphklasse PTIME charakterisiert. Wir adaptieren außerdem unsere Methoden, um einen kanonischen Beschriftungsalgorithmus für Intervallgraphen zu erhalten, der sich mit logarithmischer Platzbeschränkung (LOGSPACE) berechnen lässt. Im dritten Teil der Arbeit beschäftigt uns die ungelöste Frage, ob es eine Logik gibt, die alle Polynomialzeit-Berechnungen charakterisiert. Wir führen eine Reihe von Ranglogiken ein, die die Fähigkeit besitzen, den Rang von Matrizen über Primkörpern zu berechnen. Wir zeigen, dass diese Ergänzung um lineare Algebra robuste Logiken hervor bringt, deren Ausdrucksstärke die von FP+C übertrifft. Außerdem beweisen wir, dass Ranglogiken strikt an Ausdrucksstärke gewinnen, wenn wir die Zahl an Variablen erhöhen, die die betrachteten Matrizen indizieren. Dann bauen wir eine Brücke zur klassischen Komplexitätstheorie, indem wir über geordneten Strukturen eine Reihe von Komplexitätsklassen zwischen LOGSPACE und PTIME durch Ranglogiken charakterisieren. Die Arbeit etabliert die stärkste der Ranglogiken als Kandidat für die Charakterisierung von PTIME und legt nahe, dass Ranglogiken genauer erforscht werden müssen, um weitere Fortschritte im Hinblick auf eine Logik für Polynomialzeit zu erzielen.
Abstract (eng):
This thesis is making contributions to three strands of descriptive complexity theory. First, we adapt a representation-invariant, singly exponential-time graph canonization algorithm of Corneil and Goldberg (1984) and conclude that on structures whose relations are of arity at most 2, the logic "Choiceless Polynomial Time with Counting" precisely characterizes the polynomial-time (PTIME) properties of logarithmic-size fragments. The second contribution investigates the descriptive complexity of PTIME computations on restricted classes of graphs. We present a novel canonical form for the class of interval graphs which is definable in fixed-point logic with counting (FP+C), which shows that FP+C captures PTIME on this graph class. We also adapt our methods to obtain a canonical labeling algorithm for interval graphs which is computable in logarithmic space (LOGSPACE). The final part of this thesis takes aim at the open question whether there exists a logic which generally captures polynomial-time computations. We introduce a variety of rank logics with the ability to compute the ranks of matrices over (finite) prime fields. We argue that this introduction of linear algebra results in robust logics whose expressiveness surpasses that of FP+C. Additionally, we establish that rank logics strictly gain in expressiveness when increasing the number of variables that index the matrices we consider. Then we establish a direct connection to standard complexity theory by showing that in the presence of orders, a variety of complexity classes between LOGSPACE and PTIME can be characterized by suitable rank logics. Our exposition provides evidence that rank logics are a natural object to study and establishes the most expressive of our rank logics as a viable candidate for capturing PTIME, suggesting that rank logics need to be better understood if progress is to be made towards a logic for polynomial time.
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.
Startseite: 1 Zugriffe PDF: 4 Zugriffe Startseite: 6 Zugriffe PDF: 6 Zugriffe Startseite: 3 Zugriffe Startseite: 3 Zugriffe PDF: 4 Zugriffe PDF: 3 Zugriffe Startseite: 2 Zugriffe PDF: 5 Zugriffe PDF: 4 Zugriffe PDF: 5 Zugriffe Startseite: 1 Zugriffe PDF: 2 Zugriffe Startseite: 2 Zugriffe PDF: 6 Zugriffe PDF: 5 Zugriffe PDF: 6 Zugriffe PDF: 6 Zugriffe PDF: 8 Zugriffe PDF: 1 Zugriffe Startseite: 1 Zugriffe PDF: 14 Zugriffe Startseite: 1 Zugriffe PDF: 11 Zugriffe Startseite: 1 Zugriffe PDF: 14 Zugriffe PDF: 13 Zugriffe PDF: 18 Zugriffe PDF: 9 Zugriffe Startseite: 1 Zugriffe PDF: 10 Zugriffe Startseite: 2 Zugriffe PDF: 10 Zugriffe Startseite: 2 Zugriffe PDF: 9 Zugriffe Startseite: 2 Zugriffe PDF: 19 Zugriffe PDF: 18 Zugriffe PDF: 27 Zugriffe PDF: 21 Zugriffe PDF: 38 Zugriffe PDF: 44 Zugriffe Startseite: 2 Zugriffe PDF: 40 Zugriffe Startseite: 1 Zugriffe PDF: 64 Zugriffe Startseite: 1 Zugriffe PDF: 43 Zugriffe Startseite: 1 Zugriffe PDF: 33 Zugriffe PDF: 34 Zugriffe
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
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Monat 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
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Startseite 1 6 3 3   2     1 2           1 1 1       1 2 2 2           2 1 1 1  
PDF 4 6   4 3 5 4 5 2 6 5 6 6 8 1 14 11 14 13 18 9 10 10 9 19 18 27 21 38 44 40 64 43 33 34

Gesamtzahl der Zugriffe seit Aug 2011:

  • Startseite – 33 (0.92 pro Monat)
  • PDF – 554 (15.39 pro Monat)
 
 
Generiert am 02.10.2014, 04:47:48