Zur Kurzanzeige

2017-11-10Dissertation DOI: 10.18452/18548
Capturing Polynomial Time and Logarithmic Space using Modular Decompositions and Limited Recursion
dc.contributor.authorGrußien, Berit
dc.date.accessioned2017-11-10T11:59:25Z
dc.date.available2017-11-10T11:59:25Z
dc.date.issued2017-11-10
dc.identifier.urihttp://edoc.hu-berlin.de/18452/19244
dc.description.abstractDiese Arbeit leistet Beiträge im Bereich der deskriptiven Komplexitätstheorie. Zunächst beschäftigen wir uns mit der ungelösten Frage, ob es eine Logik gibt, welche die Klasse der Polynomialzeit-Eigenschaften (PTIME) charakterisiert. Wir betrachten Graphklassen, die unter induzierten Teilgraphen abgeschlossen sind. Auf solchen Graphklassen lässt sich die 1976 von Gallai eingeführte modulare Zerlegung anwenden. Graphen, die durch modulare Zerlegung nicht zerlegbar sind, heißen prim. Wir stellen ein neues Werkzeug vor: das Modulare Zerlegungstheorem. Es reduziert (definierbare) Kanonisierung einer Graphklasse C auf (definierbare) Kanonisierung der Klasse aller primen Graphen aus C, die mit binären Relationen auf einer linear geordneten Menge gefärbt sind. Mit Hilfe des Modularen Zerlegungstheorems zeigen wir, dass Fixpunktlogik mit Zählen (FP+C) PTIME auf der Klasse aller Permutationsgraphen und auf der Klasse aller chordalen Komparabilitätsgraphen charakterisiert. Wir beweisen zudem, dass modulare Zerlegungsbäume in Symmetrisch-Transitive-Hüllen-Logik mit Zählen (STC+C) definierbar und damit in logarithmischem Platz berechenbar sind. Weiterhin definieren wir eine neue Logik für die Komplexitätsklasse Logarithmischer Platz (LOGSPACE). Wir erweitern die Logik erster Stufe mit Zählen um einen Operator, der eine in logarithmischem Platz berechenbare Form der Rekursion erlaubt. Die resultierende Logik LREC ist ausdrucksstärker als die Deterministisch-Transitive-Hüllen-Logik mit Zählen (DTC+C) und echt in FP+C enthalten. Wir zeigen, dass LREC LOGSPACE auf gerichteten Bäumen charakterisiert. Zudem betrachten wir eine Erweiterung LREC= von LREC, die sich gegenüber LREC durch bessere Abschlusseigenschaften auszeichnet und im Gegensatz zu LREC ausdrucksstärker als die Symmetrisch-Transitive-Hüllen-Logik (STC) ist. Wir beweisen, dass LREC= LOGSPACE sowohl auf der Klasse der Intervallgraphen als auch auf der Klasse der chordalen klauenfreien Graphen charakterisiert.ger
dc.description.abstractThis theses is making contributions to the field of descriptive complexity theory. First, we look at the main open problem in this area: the question of whether there exists a logic that captures polynomial time (PTIME). We consider classes of graphs that are closed under taking induced subgraphs. For such graph classes, an effective graph decomposition, called modular decomposition, was introduced by Gallai in 1976. The graphs that are non-decomposable with respect to modular decomposition are called prime. We present a tool, the Modular Decomposition Theorem, that reduces (definable) canonization of a graph class C to (definable) canonization of the class of prime graphs of C that are colored with binary relations on a linearly ordered set. By an application of the Modular Decomposition Theorem, we show that fixed-point logic with counting (FP+C) captures PTIME on the class of permutation graphs and the class of chordal comparability graphs. We also prove that the modular decomposition tree is definable in symmetric transitive closure logic with counting (STC+C), and therefore, computable in logarithmic space. Further, we introduce a new logic for the complexity class logarithmic space (LOGSPACE). We extend first-order logic with counting by a new operator that allows it to formalize a limited form of recursion which can be evaluated in logarithmic space. We prove that the resulting logic LREC is strictly more expressive than deterministic transitive closure logic with counting (DTC+C) and that it is strictly contained in FP+C. We show that LREC captures LOGSPACE on the class of directed trees. We also study an extension LREC= of LREC that has nicer closure properties and that, unlike LREC, is more expressive than symmetric transitive closure logic (STC). We prove that LREC= captures LOGSPACE on the class of interval graphs and on the class of chordal claw-free graphs.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin
dc.rights(CC BY-NC-ND 3.0 DE) Namensnennung - Nicht-kommerziell - Keine Bearbeitung 3.0 Deutschlandger
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/de/
dc.subjectdeskriptive Komplexitätger
dc.subjectmodulare Zerlegungger
dc.subjectPolynomialzeitger
dc.subjectFixpunktlogikger
dc.subjectPermutationsgraphenger
dc.subjectchordale Komparabilitätsgraphenger
dc.subjectKanonisierungger
dc.subjectlogarithmischer Platzger
dc.subjectIntervallgraphenger
dc.subjectchordale klauenfreie Graphenger
dc.subjectdescriptive complexityeng
dc.subjectmodular decompositioneng
dc.subjectpolynomial timeeng
dc.subjectfixed-point logiceng
dc.subjectpermutation graphseng
dc.subjectchordal comparability graphseng
dc.subjectcanonizationeng
dc.subjectlogarithmic spaceeng
dc.subjectinterval graphseng
dc.subjectchordal claw-free graphseng
dc.subject.ddc004 Informatik
dc.titleCapturing Polynomial Time and Logarithmic Space using Modular Decompositions and Limited Recursion
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-110-18452/19244-7
dc.identifier.doihttp://dx.doi.org/10.18452/18548
dc.date.accepted2016-12-02
dc.contributor.refereeGrohe, Martin
dc.contributor.refereeSchweikardt, Nicole
dc.contributor.refereeKöbler, Johannes
dc.subject.rvkST 134
local.edoc.pages297
local.edoc.type-nameDissertation
bua.departmentMathematisch-Naturwissenschaftliche Fakultät

Zur Kurzanzeige