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.

<p>Ako je<em> L </em>relacijski jezik, kondenzacioni pretporedak na skupu<em> Int</em>_L <em>(X)</em> svih <em>L-</em>interpretacija nad domenom <em>X,</em> dat je sa: &rho;≼_c <em>&sigma;</em> ako postoji bijektivni homomorfizam (kondenzacija)<em> f:〈X,&rho;</em>〉&rarr;<em>〈X,&sigma;〉.</em> Odgovarajući antisimetrični količnik <em>〈Int_L</em> (X)/~_c,&le;_c〉 ~naziva se kondenzacioni poredak. Za proizvoljnu<em> L-</em>interpretaciju &rho;, klasa [&rho;]~_c&nbsp; je konveksno zatvorenje klase [&rho;]_&cong; u Booleovoj mreži 〈<em>IntL (X</em>),&sube;〉. Za <em>L</em>-interpretaciju &rho; reći ćemo da je jako reverzibilna (redom, reverzibilna, slabo reverzibilna) akko je klasa [&rho;]_&cong;&nbsp; (ili, ekvivalentno, klasa [&rho;]~_c)) singlton (redom, antilanac, konveksan skup) u Booleovoj mreži 〈<em>IntL (X)</em>,&sube;〉. U cilju ispitivanja poseta 〈<em>Int(_Lb</em>) (X)/~c,&le;c〉, za &rho;&isin;<em>Irrefl_X</em> uveden je skup D_&rho;:={[&rho;&cup;&Delta;_A ](~_c ):<em>A&sube;X</em>} i pokazano je kako je poduređenje 〈D_&rho;,&le;_c 〉 izomorfno određenom količniku partitivnog skupa<em> P(X)</em>. Fenomen reverzibilnosti relacijskih struktura igra istaknutu ulogu u istraživanju tog poduređenja.</p><p>U slučaju prebrojivog jezika <span id="cke_bm_1038S" style="display: none;">&nbsp;</span><em>L</em><span id="cke_bm_1038E" style="display: none;">&nbsp;</span> i prebrojivog domena <em>X</em>, pokazano je da su ~_c i [&rho;]~_canalitički skupovi u poljskim prostorima, redom, <em>Int_L(&omega;)&times;Int_L(&omega;) i Int_L (&omega;)</em>, i pomoću toga, pokazano ja da su, u slučaju prebrojivog jezika i domena, klase [&rho;]&cong;&nbsp; i [&rho;]~_c iste veličine, i da je to neki kardinal iz {1,&omega;,c}. Dalje je istražena hijerarhija između kondenzacione ekvivalencije, elementarne ekvivalencije, ekvimorfizma (bi-utopivosti) i drugih sličnosti <em>L-</em>struktura određenih nekim sličnostima njihovih monoida samoutapanja.</p><p>Naposletku, temeljno je istražen fenomen reverzibilnosti <em>L</em>-struktura. Data je karakterizacija jako reverzibilnih<em> L</em>-intepretacija kao onih čije su komponentne relacije definabilne formulama praznog jezika<em> L</em>_&empty;, bez kvantifikatora i parametara. Pokazano je kako su slabo reverzibilne interpretacije upravo one koje imaju svojstvo Cantor-Schrӧder-Bernstein (kraće, svojstvo CSB) za kondenzacije.</p><p>Poseban naglasak stavljen je na detektovanje relevantnih klasa reverzibilnih struktura. Pri tome, prvo su proučene strukture koje su ekstremni elementi L_{&infin;&omega;}-definabilnih klasa interpretacija, pri određenim sintaktičkim ograničenjima, a zatim su istražene nepovezane<em> L</em>_b-strukture, gde je dato nekoliko karakterizacija njihove reverzibilnosti.</p> / <p>If <em>L</em> is a relational language, the condensational preorder on the set <em>Int_L (X)</em> of all <em>L-</em>interpretations over the domain<em> X</em>, is given with: &rho;≼_c &sigma; iff there exists a bijective homomorphism (condensation) <em>f:〈X,&rho;〉&rarr;〈X,&sigma;〉. </em>The corresponding antisymmetric quotient 〈<em>Int_L (X)/</em>~_<em>c</em>,&le;__c〉 will be called the condensational order. For any <em>L</em>-interpretation &rho;, the class<em> [&rho;]~_c )</em> is the convex closure of the class [<em>&rho;</em>]&cong; in the Boolean lattice 〈<em>IntL (X</em>),&sube;〉. An <em>L</em>-interpretation &rho; is said to be strongly reversible&nbsp; (respectively, reversible, weakly reversible) iff the class <em>[&rho;]</em>&cong;&nbsp; (or, equivalently, the class<em> [&rho;]~c )</em>) is a singleton (respectively, an antichain, a convex set) in the poset 〈 <em>IntL</em> <em>(X)</em>,&sube;〉. In order to investigate the poset 〈<em>Int_(Lb ) (X)/~c,&le;_c</em>〉, for &rho;&isin;<em> IrreflX</em> the following set is defined <em>D_&rho;</em>:={[&rho;&cup;&Delta;_A ]_~c :A&sube;X}. It is shown that the suborder 〈<em>D_&rho;,</em>&le;_c 〉 is isomorphic to a certain quotient of the power set <em>P(X)</em>. The phenomenon of reversibility plays prominent role in the investigation of that suborder.<br />In the case of a countable language<em> L</em> and a countable domain&nbsp; <em>X</em>, it is shown that ~c&nbsp; and [<em>&rho;]__~c&nbsp;</em>are analytic sets in the Polish spaces, respectively,<em> IntL (&omega;)&times; IntL (&omega;)</em> and <em>Int_L (&omega;)</em>, and, using those results, in the case of a countable language and domain it is shown that the classes <em>[&rho;]_</em>&cong;&nbsp; and <em>[&rho;]~_c&nbsp;</em>are of the same size, and that it is a cardinals from _{{1,&omega;,c}. N}ext, the hierarchy between condensational equivalence, elementary equivalence, equimorphism (bi- embedability) and other similarities of <em>L</em>-structures, determined by some similarities of their self-embedding monoids, is investigated.<br />In the last part, the phenomenon of reversibility of<em> L</em>-structures is investigated. Strongly reversible <em>L</em>-intepretations are characterized as those whose component relations are definable by the formulae of the empty language<em> L_&empty;, </em>without quantifiers and parameters. It is shown that weakly reversible interpretations are exactly those having the property Cantor-Schrӧder-Bernstein (shorter, the property CSB) for condensations.<br />Particular emphasis is put on detecting relevant classes of reversible structures. First, the structures that are extreme elements of<em> L</em>_{&infin;&omega;}-definable classes of interpretations, under certain syntactical restrictions, are investigated. Following that, disconnected Lb-structures are investigated, where several equivalents of their reversibility are proven.</p>