Diese 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. / This 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.

Der Bereich von Sterben, Tod und Trauer gehört als indirekte oder auch direkte Todeswirklichkeit zum Alltag von Vor- und Grundschulkindern. Seit den 1990er Jahren finden diese Themen zunehmend Eingang in die deutschsprachigen Bilderbücher und werden dort anhand verschiedener literarästhetischer Erzählstrategien auf der Text- sowie Bildebene und deren Wechselverhältnis diskutiert. Die vorliegende Untersuchung ordnet das Primärtextkorpus deutschsprachiger Bilderbücher zu Sterben, Tod und Trauer anhand eines untersuchungseigenen inhaltsbezogenen Rubrikenmodelles. Der für die qualitative Beurteilung der untersuchten Bilderbücher entwickelte Katalog von Analysekriterien berücksichtigt sowohl gattungsspezifische Forschungsarbeiten als auch Studien zum Verhältnis von Kind und Tod. Um in den Bilderbüchern tabuisierte, kanonisierte und innovative Erzählstrategien von Tod und Trauer nicht nur herauszuarbeiten, sondern auch komparatistisch in einen europäischen Kontext einzuordnen, wird der Untersuchung deutschsprachiger Bilderbücher die Diskussion der Entwicklung des Themenfeldes im schwedischen Bilderbuch gegenüber gestellt. Das Innovationspotenzial, das ausgewählte seit den 1970er Jahren veröffentlichte schwedische Bilderbücher für die Entwicklung des Themenbereiches Tod und Trauer im deutschsprachigen Bilderbuchmarkt besitzen, wird insbesondere in den Grenzbereichen zwischen tradierten sowie innovativen Erzählstrategien deutlich. Sowohl in den zusammenfassenden Betrachtungen der einzelnen inhaltsbezogenen Unterrubriken, die das deutschsprachige sowie schwedische Primärtextkorpus gliedern, als auch in den einzelanalytischen Abschnitten werden bestehende Kanonisierungs- sowie Tabuisierungstendenzen in Bezug auf die Darstellung einzelner Themenaspekte von Tod und Trauer deutlich, wenngleich diese zunehmend in Auflösung begriffen und in einigen Unterrubriken stärker ausgeprägt sind als in anderen. / Dying, death and grief are a direct or indirect part of the reality of preschool and primary school children. Since the 1990s, these topics increasingly find their way into German picture books, where they are discussed using different literary-aesthetic narrative strategies through text and images as well as their interrelationship. The present study maps the primary text corpus of German picture books on dying, death and grief by means of a research-based content-related category model. The catalogue of analytic criteria developed for the qualitative assessment of the examined picture books takes into account both genre-specific research and studies on the attitudes of children toward death. In order not only to elaborate on tabooed, canonized and innovative narrative strategies of death and grief in picture books, but also to place them in a comparative European context, the study of German picture books is set against the discussion of the development of these topics in Swedish picture books. The innovation potential, which selected Swedish picture books published since the 1970s contain for the development of the theme of death and grief in the German picture book market, becomes particularly evident in the border areas between traditional and innovative narrative strategies. Both in the summary of the individual content-related subcategories, which classify the German and Swedish primary text corpuses, as well as in the individual analytic sections, existing tendencies to canonize or taboo with regard to the representation of individual aspects of death and grief become clear, though they are in a process of disintegration and are more pronounced in some subcategories than in others.