• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 11
  • 9
  • 3
  • Tagged with
  • 21
  • 15
  • 12
  • 10
  • 5
  • 5
  • 5
  • 5
  • 4
  • 4
  • 4
  • 4
  • 4
  • 4
  • 4
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
11

Evolutionäre Referenzmodelle

Lehrmann, Sina 15 September 2014 (has links) (PDF)
Konzeptuelle Modelle sind zur Gestaltung und Steuerung von Informationssystemen ein akzeptiertes und weit verbreitetes Instrument. Sie werden sowohl zur Gestaltung der Organisationsstruktur als auch zur Entwicklung der unterstützenden IT-Systeme verwendet. Für diesen Aufgabenbereich existiert eine hohe Nachfrage nach externer Unterstützung, da spezifische Fachkenntnisse und Erfahrungen notwendig sind. In diesem Zusammenhang werden seit Jahrzehnten Ansätze zur Wiederverwendung in Wissenschaft und Praxis diskutiert. Die Akzeptanz und Verbreitung von explizit zur Wiederverwendung konstruierten Modellen (Referenzmodelle) bleiben jedoch deutlich hinter den Erwartungen zurück. Die vorliegende Arbeit trägt zur Untersuchung möglicher Ursachen für den ausbleibenden Erfolg von Referenzmodellen bei. Der Forschung liegt die Vermutung zugrunde, dass die Potentiale von Referenzmodellen nicht zufriedenstellend ausgeschöpft werden können, weil die existierenden bzw. verwendeten Modellierungsmethoden die theoretischen Anforderungen an die Wiederverwendung von modellhaft dargestellten Lösungen zur Unternehmensgestaltung nicht erfüllen. Die vorliegende Arbeit fasst neun Einzelpublikationen zum Themenbereich Evolutionäre Referenzmodelle zu einer kumulativen Dissertation zusammen. Es werden in einem argumentativdeduktiven Verfahren konstruktivistische Theorien zur systematischen Weiterentwicklung und Wiederverwendung konzeptueller Unternehmensmodelle untersucht. Die auf dieseWeise resultierende Erweiterung der allgemeinen Modelltheorie wurde ihrerseits argumentativ-konzeptionell mit Hilfe von semiformalen Argumentationsmodellen aufbereitet. Im Ergebnis werden ein theoretisches Rahmenwerk zur evolutionären Referenzmodellierung präsentiert und 23 konzeptionelle Anforderungen definiert, die eine gezielte Methodenentwicklung für die evolutionäre Referenzmodellierung steuern sollen.
12

Fraïssé-Hrushovski predimensions on nilpotent Lie algebras

Amantini, Andrea 30 June 2011 (has links)
In dieser Arbeit wird das Fraïssé-Hrushowskis Amalgamationsverfahren in Zusammenhang mit nilpotenten graduierten Lie Algebren über einem endlichen Körper untersucht. Die Prädimensionen die in der Konstruktion auftauchen sind mit dem gruppentheoretischen Begriff der Defizienz zu vergleichen, welche auf homologische Methoden zurückgeführt werden kann. Darüber hinaus wird die Magnus-Lazardsche Korrespondenz zwischen den oben genannten Lie Algebren und nilpotenten Gruppen von Primzahl-Exponenten beschrieben. Dabei werden solche Gruppen durch die Baker-Haussdorfsche Formel in den entsprechenden Algebren definierbar interpretiert. Es wird eine omega-stabile Lie Algebra von Nilpotenzklasse 2 und Morleyrang omega + omega erhalten, indem man eine unkollabierte Version der von Baudisch konstruierten "new uncountably categorical group" betrachtet. Diese wird genau analysiert. Unter anderem wird die Unabhängigkeitsrelation des Nicht-Gabelns durch die Konfiguration des freien Amalgams charakterisiert. Mittels eines induktiven Ansatzes werden die Grundlagen entwickelt, um neue Prädimensionen für Lie Algebren der Nilpotenzklassen größer als zwei zu schaffen. Dies erweist sich als wesentlich schwieriger als im Fall 2. Wir konzentrieren uns daher auf die Nilpotenzklasse 3, als Induktionsbasis des oben genannten Prozesses. In diesem Fall wird die Invariante der Defizienz auf endlich erzeugte Lie Algebren adaptiert. Erstes Hauptergebnis der Arbeit ist der Nachweis dass diese Definition zu einem vernüftigen Begriff selbst-genügender Erweiterungen von Lie Algebren führt und sehr nah einer gewünschten Prädimension im Hrushovskischen Sinn ist. Wir zeigen – als zweites Hauptergebnis – ein erstes Amalgamationslemma bezüglich selbst-genügender Einbettungen. / In this work, the so called Fraïssé-Hrushowski amalgamation is applied to nilpotent graded Lie algebras over the p-elements field with p a prime. We are mainly concerned with the uncollapsed version of the original process. The predimension used in the construction is compared with the group theoretical notion of deficiency, arising from group Homology. We also describe in detail the Magnus-Lazard correspondence, to switch between the aforementioned Lie algebras and nilpotent groups of prime exponent. In this context, the Baker-Hausdorff formula allows such groups to be definably interpreted in the corresponding algebras. Starting from the structures which led to Baudisch’ new uncountably categorical group, we obtain an omega-stable Lie algebra of nilpotency class 2, as the countable rich Fraïssé limit of a suitable class of finite Lie algebras. We study the theory of this structure in detail: we show its Morley rank is omega+omega and a complete description of non-forking independence is given, in terms of free amalgams. In a second part, we develop a new framework for the construction of deficiency-predimensions among graded Lie algebras of nilpotency class higher than 2. This turns out to be considerably harder than the previous case. The nil-3 case in particular has been extensively treated, as the starting point of an inductive procedure. In this nilpotency class, our main results concern a suitable deficiency function, which behaves for many aspects like a Hrushovski predimension. A related notion of self-sufficient extension is given. We also prove a first amalgamation lemma with respect to self-sufficient embeddings.
13

Lambda-Strukturen und s-Strukturen

Fuchs, Gunter 19 June 2003 (has links)
In dieser Arbeit werden lambda-Strukturen und s-Strukturen eingeführt, und Funktionen S und Lambda entwickelt, die lambda-Strukturen auf s-Strukturen abbilden und umgekehrt. lambda-Strukturen sind eng verwandt mit den in von Jensen untersuchten Prämäusen (iterierbare Prämäuse dieser Art sind lambda-Strukturen), und s-Strukturen wurden in Anlehnung an die von Mitchell und Steel betrachteten Prämäuse definiert. Wieder sind iterierbare Prämäuse dieser Art auch s-Strukturen. Für die Definition dieser Strukturen wurde eine neue, schwache Form der initial segment condition entwickelt (die s'-ISC), die stark genug für die Anwendungen ist. Um zu zeigen, dass die hier entwickelten Funktionen die gewünschte Korrespondenz realisieren, wurden Methoden zur Übersetzung von Formeln entwickelt, die teilweise sehr allgemein gehalten sind. So ist die Übersetzung von Sigma-1-Formeln, die in einer Nachfolgerstufe der Jensen-Hierarchie gelten, in entsprechende Sigma-omega-Formeln in der Vorgängerstufe, anwendbar auf beliebige J-Strukturen. Es werden normale s-Iterationen eingeführt, die den normalen Iterationen von Prämäusen im Sinne von Mitchell-Steel nachgebildet sind, aber auf lambda-Strukturen angewandt werden, und es wird gezeigt, dass die entwickelten Funktionen komponentenweise auf Iterationen angewandt werden können, um normale s-Iterationen von lambda-Strukturen in normale Iterationen von s-Strukturen zu übersetzen, und umgekehrt. Mit diesen Methoden lassen sich auch Iterationsstrategien übersetzen, und man erhält, dass die entwickelten Funktionen normal s-iterierbare lambda-Strukturen auf normal iterierbare s-Strukturen abbilden, und umgekehrt. Auch bleiben die wesentlichen feinstrukturellen Größen, wie bspw. Projekta, und unter gewissen Voraussetzungen (soundness und 1-solidity) auch die Standard-Parameter, erhalten. / In this work we introduce lambda-structures and s-structures, and develop functions S and Lambda, which map lambda-structures to s-structures and vice versa. lambda-structures are closely related to the premice studied in recent work of Jensen (iterable premice of this kind are lambda-structures), and s-structures were defined with the premice developed by Mitchell and Steel in mind. Again, iterable premice of this kind are s-structures. For the definition of these structures, a new form of the initial segment condition condition, called s'-ISC, was developed, which is a common weakening of the versions used in by Steel and Jensen. It still suffices for the applications. In order to show that the functions introduced establish the desired correspondence, we developed methods for translating formulae, which in part are very generally applicable. For instance, the translation of Sigma-1-formulae which hold in a successor level of the Jensen-hierarchy into corresponding Sigma-omega-formulae in the predecessor level, can be applied to arbitrary J-structures. We introduce normal s-iterations, which have been designed so as to rebuild the iterations of premice in the sense of Mitchell-Steel but are applied to lambda-structures. It is shown that the translation functions can be applied component-wise to normal iterations, in order to translate normal s-iterations of lambda-structures into normal iterations of s-structures, and vice versa. Using these methods, we can also translate iteration strategies and the result is that the functions introduced in this work map normally s-iterable lambda-structures to normally iterable s-structures, and vice versa. Also,the fundamental fine structural notions, such as projecta, and under additional hypotheses (soundness and 1-solidity) standard-parameters, are preserved.
14

Randomness in complexity theory and logics

Eickmeyer, Kord 01 September 2011 (has links)
Die vorliegende Dissertation besteht aus zwei Teilen, deren gemeinsames Thema in der Frage besteht, wie mächtig Zufall als Berechnungsressource ist. Im ersten Teil beschäftigen wir uns mit zufälligen Strukturen, die -- mit hoher Wahrscheinlichkeit -- Eigenschaften haben können, die von Computeralgorithmen genutzt werden können. In zwei konkreten Fällen geben wir bis dahin unbekannte deterministische Konstruktionen solcher Strukturen: Wir derandomisieren eine randomisierte Reduktion von Alekhnovich und Razborov, indem wir bestimmte unbalancierte bipartite Expandergraphen konstruieren, und wir geben eine Reduktion von einem Problem über bipartite Graphen auf das Problem, den minmax-Wert in Dreipersonenspielen zu berechnen. Im zweiten Teil untersuchen wir die Ausdrucksstärke verschiedener Logiken, wenn sie durch zufällige Relationssymbole angereichert werden. Unser Ziel ist es, Techniken aus der deskriptiven Komplexitätstheorie für die Untersuchung randomisierter Komplexitätsklassen nutzbar zu machen, und tatsächlich können wir zeigen, dass unsere randomisierten Logiken randomisierte Komlexitätsklassen einfangen, die in der Komplexitätstheorie untersucht werden. Unter Benutzung starker Ergebnisse über die Logik erster Stufe und die Berechnungsstärke von Schaltkreisen beschränkter Tiefe geben wir sowohl positive als auch negative Derandomisierungsergebnisse für unsere Logiken. Auf der negativen Seite zeigen wir, dass randomisierte erststufige Logik gegenüber normaler erststufiger Logik an Ausdrucksstärke gewinnt, sogar auf Strukturen mit einer eingebauten Additionsrelation. Außerdem ist sie nicht auf geordneten Strukturen in monadischer zweitstufiger Logik enthalten, und auch nicht in infinitärer Zähllogik auf beliebigen Strukturen. Auf der positiven Seite zeigen wir, dass randomisierte erststufige Logik auf Strukturen mit einem unären Vokabular derandomisiert werden kann und auf additiven Strukturen in monadischer Logik zweiter Stufe enthalten ist. / This thesis is comprised of two main parts whose common theme is the question of how powerful randomness as a computational resource is. In the first part we deal with random structures which possess -- with high probability -- properties than can be exploited by computer algorithms. We then give two new deterministic constructions for such structures: We derandomise a randomised reduction due to Alekhnovich and Razborov by constructing certain unbalanced bipartite expander graphs, and we give a reduction from a problem concerning bipartite graphs to the problem of computing the minmax-value in three-player games. In the second part we study the expressive power of various logics when they are enriched by random relation symbols. Our goal is to bridge techniques from descriptive complexity with the study of randomised complexity classes, and indeed we show that our randomised logics do capture complexity classes under study in complexity theory. Using strong results on the expressive power of first-order logic and the computational power of bounded-depth circuits, we give both positive and negative derandomisation results for our logics. On the negative side, we show that randomised first-order logic gains expressive power over standard first-order logic even on structures with a built-in addition relation. Furthermore, it is not contained in monadic second-order logic on ordered structures, nor in infinitary counting logic on arbitrary structures. On the positive side, we show that randomised first-order logic can be derandomised on structures with a unary vocabulary and is contained in monadic second-order logic on additive structures.
15

Modelling in Mathematics and Informatics: How Should the Elevators Travel so that Chaos Will Stop?

Filler, Andreas 13 April 2012 (has links) (PDF)
Didactic proposals on modelling in mathematics education mostly give priority to models which describe, explain as well as partially forecast and provide mathematical solutions to real situations. A view of the modelling concept of informatics, which also initiates rapidly generalised deliberations of models, can also make a contribution to the spectrum of models, which are treated in a meaningful sense in mathematics lessons so as to expand some interesting aspects. In this paper, this is illustrated by means of conceptual design models – and, here, especially of process models – using the example of elevator organisation in a multi-storey construction.
16

Evolutionäre Referenzmodelle: Anforderungen an eine methodische Unterstützung zur systematischen Wiederverwendung und Weiterentwicklung von modellhaft aufbereitetem Wissen

Lehrmann, Sina 16 July 2014 (has links)
Konzeptuelle Modelle sind zur Gestaltung und Steuerung von Informationssystemen ein akzeptiertes und weit verbreitetes Instrument. Sie werden sowohl zur Gestaltung der Organisationsstruktur als auch zur Entwicklung der unterstützenden IT-Systeme verwendet. Für diesen Aufgabenbereich existiert eine hohe Nachfrage nach externer Unterstützung, da spezifische Fachkenntnisse und Erfahrungen notwendig sind. In diesem Zusammenhang werden seit Jahrzehnten Ansätze zur Wiederverwendung in Wissenschaft und Praxis diskutiert. Die Akzeptanz und Verbreitung von explizit zur Wiederverwendung konstruierten Modellen (Referenzmodelle) bleiben jedoch deutlich hinter den Erwartungen zurück. Die vorliegende Arbeit trägt zur Untersuchung möglicher Ursachen für den ausbleibenden Erfolg von Referenzmodellen bei. Der Forschung liegt die Vermutung zugrunde, dass die Potentiale von Referenzmodellen nicht zufriedenstellend ausgeschöpft werden können, weil die existierenden bzw. verwendeten Modellierungsmethoden die theoretischen Anforderungen an die Wiederverwendung von modellhaft dargestellten Lösungen zur Unternehmensgestaltung nicht erfüllen. Die vorliegende Arbeit fasst neun Einzelpublikationen zum Themenbereich Evolutionäre Referenzmodelle zu einer kumulativen Dissertation zusammen. Es werden in einem argumentativdeduktiven Verfahren konstruktivistische Theorien zur systematischen Weiterentwicklung und Wiederverwendung konzeptueller Unternehmensmodelle untersucht. Die auf dieseWeise resultierende Erweiterung der allgemeinen Modelltheorie wurde ihrerseits argumentativ-konzeptionell mit Hilfe von semiformalen Argumentationsmodellen aufbereitet. Im Ergebnis werden ein theoretisches Rahmenwerk zur evolutionären Referenzmodellierung präsentiert und 23 konzeptionelle Anforderungen definiert, die eine gezielte Methodenentwicklung für die evolutionäre Referenzmodellierung steuern sollen.
17

Modelling in Mathematics and Informatics: How Should the Elevators Travel so that Chaos Will Stop?

Filler, Andreas 13 April 2012 (has links)
Didactic proposals on modelling in mathematics education mostly give priority to models which describe, explain as well as partially forecast and provide mathematical solutions to real situations. A view of the modelling concept of informatics, which also initiates rapidly generalised deliberations of models, can also make a contribution to the spectrum of models, which are treated in a meaningful sense in mathematics lessons so as to expand some interesting aspects. In this paper, this is illustrated by means of conceptual design models – and, here, especially of process models – using the example of elevator organisation in a multi-storey construction.
18

Mechanische Simulation der Interaktion Sportler-Sportgerät-Umwelt

Schwanitz, Stefan 12 May 2015 (has links) (PDF)
In der vorliegenden Arbeit wird eine Methodik zur Entwicklung mechanischer Simulationen der Interaktion Sportler-Sportgerät-Umwelt zur Untersuchung der Funktionalität von Sportgeräten konzipiert und vorgestellt. Die mechanische Simulation ist die gegenständliche Nachbildung spezieller Teilaspekte des Sportlers, z.B. der Körperform, der Trägheitseigenschaften, der Masse, der Interaktionskräfte zur Umwelt oder charakteristischer Bewegungsabläufe zum Zweck der Durchführung gezielter Experimente zur Untersuchung des dynamischen Systemverhaltens Sportler-Sportgerät-Umwelt. Dazu werden drei Fallbeispiele aus der Forschungstätigkeit der Arbeitsgruppe HLST an der Technischen Universität Chemnitz mit Methoden zur Verifikation von Simulationsmodellen – dem strukturierten Durchgehen, der Validierung im Dialog und dem Schreibtischtest – analysiert. Die Analyseergebnisse werden in eine Grobstruktur eingebettet, die aus relevanten Vorarbeiten zur Anwendung der Allgemeinen Modelltheorie abgeleitet ist. Die in den jeweiligen Fallbeispielen verwendeten Prozessschritte, Methoden und Werkzeuge werden dargestellt und die Entwicklungsergebnisse erörtert. Im Abschluss jedes Fallbeispiels wird der Entwicklungsprozess anhand von einheitlichen Kriterien bewertet. In einem abschließenden Schritt erfolgt die Zusammenführung der im Stand der Technik dargelegten Grundlagen und der in den drei Fallbeispielen gewonnenen Informationen zu einer strukturieren und kommentierten Methodik. / In this dissertation a methodology is conceived that aims to structure the development process of test arrangements that mechanically simulate the interaction of athlete, sports equipment and environment. Mechanical simulation in this context is defined as the physical replication of specific properties of the athlete (e.g. the shape of the human body, body weight, joint kinematics, inertia, external forces in specific movements) in order to conduct experiments to investigate the dynamic behavior of the system athlete-equipment-environment. Therefore, three case studies of mechanical simulation models that have been developed at Technische Universität Chemnitz are analyzed by applying the validation and verification methods “structured walkthrough”, “face validity” and “desk checking”. The results of that analysis are embedded into a framework that is derived by literature review on applied model theory. For each of the three development processes the procedure model is identified and main tools and methods are discussed. Every case study is finally assessed by using standardized evaluation criterions. Finally, the main findings of the analysis of the case studies as well as knowledge obtained by reviewing the state of the art in model theory and simulation methods are used to build up a structured and commentated guideline.
19

On Invariant Formulae of First-Order Logic with Numerical Predicates

Harwath, Frederik 12 December 2018 (has links)
Diese Arbeit untersucht ordnungsinvariante Formeln der Logik erster Stufe (FO) und einiger ihrer Erweiterungen, sowie andere eng verwandte Konzepte der endlichen Modelltheorie. Viele Resultate der endlichen Modelltheorie nehmen an, dass Strukturen mit einer Einbettung ihres Universums in ein Anfangsstück der natürlichen Zahlen ausgestattet sind. Dies erlaubt es, beliebige Relationen (z.B. die lineare Ordnung) und Operationen (z.B. Addition, Multiplikation) von den natürlichen Zahlen auf solche Strukturen zu übertragen. Die resultierenden Relationen auf den endlichen Strukturen werden als numerische Prädikate bezeichnet. Werden numerische Prädikate in Formeln verwendet, beschränkt man sich dabei häufig auf solche Formeln, deren Wahrheitswert auf endlichen Strukturen invariant unter Änderungen der Einbettung der Strukturen ist. Wenn das einzige verwendete numerische Prädikat eine lineare Ordnung ist, spricht man beispielsweise von ordnungsinvarianten Formeln. Die Resultate dieser Arbeit können in drei Teile unterteilt werden. Der erste Teil betrachtet die Lokalitätseigenschaften von FO-Formeln mit Modulo-Zählquantoren, die beliebige numerische Prädikate invariant nutzen. Der zweite Teil betrachtet FO-Sätze, die eine lineare Ordnung samt der zugehörigen Addition auf invariante Weise nutzen, auf endlichen Bäumen. Es wird gezeigt, dass diese dieselben regulären Baumsprachen definieren, wie FO-Sätze ohne numerische Prädikate mit bestimmten Kardinalitätsprädikaten. Für den Beweis wird eine algebraische Charakterisierung der in dieser Logik definierbaren Baumsprachen durch Operationen auf Bäumen entwickelt. Der dritte Teil der Arbeit beschäftigt sich mit der Ausdrucksstärke und der Prägnanz von FO und Erweiterungen von FO auf Klassen von Strukturen beschränkter Baumtiefe. / This thesis studies the concept of order-invariance of formulae of first-order logic (FO) and some of its extensions as well as other closely related concepts from finite model theory. Many results in finite model theory assume that structures are equipped with an embedding of their universe into an initial segment of the natural numbers. This allows to transfer arbitrary relations (e.g. linear order) and operations (e.g. addition, multiplication) on the natural numbers to structures. The arising relations on the structures are called numerical predicates. If formulae use these numerical predicates, it is often desirable to consider only such formulae whose truth value in finite structures is invariant under changes to the embeddings of the structures. If the numerical predicates include only a linear order, such formulae are called order-invariant. We study the effect of the invariant use of different kinds of numerical predicates on the expressive power of FO and extensions thereof. The results of this thesis can be divided into three parts. The first part considers the locality and non-locality properties of formulae of FO with modulo-counting quantifiers which may use arbitrary numerical predicates in an invariant way. The second part considers sentences of FO which may use a linear order and the corresponding addition in an invariant way and obtains a characterisation of the regular finite tree languages which can be defined by such sentences: these are the same tree languages which are definable by FO-sentences without numerical predicates with certain cardinality predicates. For the proof, we obtain a characterisation of the tree languages definable in this logic in terms of algebraic operations on trees. The third part compares the expressive power and the succinctness of different ex- tensions of FO on structures of bounded tree-depth.
20

The structure of graphs and new logics for the characterization of Polynomial Time

Laubner, Bastian 14 June 2011 (has links)
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. / 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.

Page generated in 0.0775 seconds