We explore the possibility of automating <i>NP</i>-hardness reductions. We motivate the problem from an artificial intelligence perspective, then propose the use of second-order existential (<i>SO</i>&#8707;) logic as representation language for decision problems. Building upon the theoretical framework of J. Antonio Medina, we explore the possibility of implementing seven syntactic operators. Each operator transforms <i>SO</i>&#8707; sentences in a way that preserves <i>NP</i>-completeness. We subsequently propose a program which implements these operators. We discuss a number of theoretical and practical barriers to this task. We prove that determining whether two <i>SO</i>&#8707; sentences are equivalent is as hard as GRAPH ISOMORPHISM, and prove that determining whether an arbitrary <i>SO</i>&#8707; sentence represents an <i>NP</i>-complete problem is undecidable.

We investigate F-Borel topological spaces. We focus on finding out how a complexity of a space depends on where the space is embedded. Of a particular interest is the problem of determining whether a complexity of given space X is absolute (that is, the same in every compactification of X). We show that the complexity of metrizable spaces is absolute and provide a sufficient condition for a topological space to be absolutely Fσδ. We then investigate the relation between local and global complexity. To improve our understanding of F-Borel spaces, we introduce different ways of representing an F-Borel set. We use these tools to construct a hierarchy of F-Borel spaces with non-absolute complexity, and to prove several other results. 1

We explore the possibility of automating <i>NP</i>-hardness reductions. We motivate the problem from an artificial intelligence perspective, then propose the use of second-order existential (<i>SO</i>&#8707;) logic as representation language for decision problems. Building upon the theoretical framework of J. Antonio Medina, we explore the possibility of implementing seven syntactic operators. Each operator transforms <i>SO</i>&#8707; sentences in a way that preserves <i>NP</i>-completeness. We subsequently propose a program which implements these operators. We discuss a number of theoretical and practical barriers to this task. We prove that determining whether two <i>SO</i>&#8707; sentences are equivalent is as hard as GRAPH ISOMORPHISM, and prove that determining whether an arbitrary <i>SO</i>&#8707; sentence represents an <i>NP</i>-complete problem is undecidable.

ROCHA, Thiago Alves. Complexidade descritiva de classes de complexidade probabilísticas de tempo polinomial e das classes ⊕P e NP∩coNP através de lógicas com quantificadores de segunda ordem. 2014. 81 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T18:02:32Z No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-22T12:36:28Z (GMT) No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) / Made available in DSpace on 2016-07-22T12:36:28Z (GMT). No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) Previous issue date: 2014 / Many computable problems can be solved more efficiently or in a more natural way through probabilistic algorithms, which shows that the use of such algorithms is quite relevant in Computer Science. However, probabilistic algorithms may return a wrong answer with a certain probability. Also, the use of probabilistic algorithms does not solve problems that are not computable. In Computational Complexity, the complexity of a problem is characterized based on the amount of computational resources, such as space and time, needed to solve it. Problems that have the same complexity compose the same class. The computational complexity classes are related by a hierarchy. In Descriptive Complexity, a logic is used to express problems and capture computational complexity classes in order to express all and only the problems of this class. Thus, the complexity of a problem does not depend on physical factors, such as time and space, but only on the expressiveness of the logic that defines it. Important results of the area states that several classes of computational complexity can be characterized by a logic. For example, the class NP has been shown equivalent to the class of problems expressed by the existential fragment of Second-Order Logic. This close relationship between these areas allows some results about Logics to be transferred to Computational Complexity and vice versa. Despite of the importance of probabilistic algorithms and of Descriptive Complexity, there are few results on the characterization, by a logic, of probabilistic computational complexity classes. In this work, we show characterizations for each of the polinomial time probabilistic complexity classes. In our results, we use second-order generalized quantifiers to simulate the acceptance of the nondeterministic machines of these classes. We found Logical characterizations in the literature only for classes PP and BPP. In the first case, the logic employed was the first-order added by a quantifier most of second-order. With the approach established in this work, we obtain an alternative proof for the characterization of PP. With the same methodology, we also characterize the class ⊕P through a logic with a second-order parity quantifier. In the case of BPP , there was a result that used a logic with probabilistic semantics. Using our approach of generalized quantifiers, we obtain an alternative characterization for this class. With the same method, we were able to characterize the probabilistic semantic classes RP, coRP, ZPP and the semantic class NP ∩ coNP. Finally, we show an application of Descriptive Complexity results in the creation of algorithms from a logic specification. / Vários problemas computáveis podem ser resolvidos de maneira mais eficiente ou mais natural através de algoritmos probabilísticos, o que mostra que o uso de tais algoritmos é bastante relevante em computação. Entretanto, os algoritmos probabilísticos podem retornar uma resposta errada com uma certa probabilidade. Observe, ainda que o uso de algoritmos probabilísticos não resolve problemas não computáveis. A Complexidade Computacional caracteriza a complexidade de um problema a partir da quantidade de recursos computacionais, como espaço e tempo, para resolvê-lo. Problemas que tem a mesma complexidade compõem uma classe. As classes de complexidade computacional são relacionadas através de uma hierarquia. A Complexidade Descritiva usa lógicas para expressar os problemas e capturar classes de complexidade computacional no sentido de expressar todos, e apenas, os problemas desta classe. Dessa forma, a complexidade de um problema não depende de fatores físicos, como tempo e espaço, mas apenas da expressividade da lógica que o define. Resultados importantes da área mostraram que várias classes de complexidade computacional podem ser caracterizadas por lógicas. Por exemplo, a classe NP foi mostrada equivalente à classe dos problemas expressos pelo fragmento existencial da Lógica de Segunda Ordem. Este estreito relacionamento entre tais áreas permite que alguns resultados da área de Lógica sejam transferidos para a de Complexidade Computacional e vice-versa. Apesar da importância de algoritmos probabilísticos e da Complexidade Descritiva, existem poucos resultados de caracterização, por lógicas, das classes de complexidade computacional probabilísticas. Neste trabalho, buscamos mostrar caracterizações para cada uma das classes de complexidade probabilísticas de tempo polinomial. Nos nossos resultados, utilizamos quantificadores generalizados de segunda ordem para simular a aceitação das máquinas não-determinísticas dessas classes. Achamos caracterizações lógicas na literatura apenas para as classes PP e BPP. No primeiro caso, a lógica utilizada era a de primeira ordem adicionada de um quantificador maioria de segunda ordem. Com a abordagem criada neste trabalho, conseguimos obter uma prova alternativa para a caracterização de PP. Com essa mesma metodologia, também conseguimos caracterizar a classe ⊕P através de uma lógica com um quantificador de paridade. No caso de BPP, existia um resultado que utilizava uma lógica com semântica probabilística. Usando nossa abordagem de quantificadores generalizados, conseguimos obter uma caracterização alternativa para essa classe. Com o mesmo método, conseguimos caracterizar as classes probabilísticas semânticas RP, coRP, ZPP e a classe semântica NP∩coNP. Por fim, mostramos uma aplicação dos resultados de Complexidade Descritiva na criação de algoritmos através de uma especificação lógica.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / VÃrios problemas computÃveis podem ser resolvidos de maneira mais eficiente ou mais natural atravÃs de algoritmos probabilÃsticos, o que mostra que o uso de tais algoritmos à bastante relevante em computaÃÃo. Entretanto, os algoritmos probabilÃsticos podem retornar uma resposta errada com uma certa probabilidade. Observe, ainda que o uso de algoritmos probabilÃsticos nÃo resolve problemas nÃo computÃveis. A Complexidade Computacional caracteriza a complexidade de um problema a partir da quantidade de recursos computacionais, como espaÃo e tempo, para resolvÃ-lo. Problemas que tem a mesma complexidade compÃem uma classe. As classes de complexidade computacional sÃo relacionadas atravÃs de uma hierarquia. A Complexidade Descritiva usa lÃgicas para expressar os problemas e capturar classes de complexidade computacional no sentido de expressar todos, e apenas, os problemas desta classe. Dessa forma, a complexidade de um problema nÃo depende de fatores fÃsicos, como tempo e espaÃo, mas apenas da expressividade da lÃgica que o define. Resultados importantes da Ãrea mostraram que vÃrias classes de complexidade computacional podem ser caracterizadas por lÃgicas. Por exemplo, a classe NP foi mostrada equivalente à classe dos problemas expressos pelo fragmento existencial da LÃgica de Segunda Ordem. Este estreito relacionamento entre tais Ãreas permite que alguns resultados da Ãrea de LÃgica sejam transferidos para a de Complexidade Computacional e vice-versa. Apesar da importÃncia de algoritmos probabilÃsticos e da Complexidade Descritiva, existem poucos resultados de caracterizaÃÃo, por lÃgicas, das classes de complexidade computacional probabilÃsticas. Neste trabalho, buscamos mostrar caracterizaÃÃes para cada uma das classes de complexidade probabilÃsticas de tempo polinomial. Nos nossos resultados, utilizamos quantificadores generalizados de segunda ordem para simular a aceitaÃÃo das mÃquinas nÃo-determinÃsticas dessas classes. Achamos caracterizaÃÃes lÃgicas na literatura apenas para as classes PP e BPP. No primeiro caso, a lÃgica utilizada era a de primeira ordem adicionada de um quantificador maioria de segunda ordem. Com a abordagem criada neste trabalho, conseguimos obter uma prova alternativa para a caracterizaÃÃo de PP. Com essa mesma metodologia, tambÃm conseguimos caracterizar a classe &#8853;P atravÃs de uma lÃgica com um quantificador de paridade. No caso de BPP, existia um resultado que utilizava uma lÃgica com semÃntica probabilÃstica. Usando nossa abordagem de quantificadores generalizados, conseguimos obter uma caracterizaÃÃo alternativa para essa classe. Com o mesmo mÃtodo, conseguimos caracterizar as classes probabilÃsticas semÃnticas RP, coRP, ZPP e a classe semÃntica NP&#8745;coNP. Por fim, mostramos uma aplicaÃÃo dos resultados de Complexidade Descritiva na criaÃÃo de algoritmos atravÃs de uma especificaÃÃo lÃgica. / Many computable problems can be solved more efficiently or in a more natural way through probabilistic algorithms, which shows that the use of such algorithms is quite relevant in Computer Science. However, probabilistic algorithms may return a wrong answer with a certain probability. Also, the use of probabilistic algorithms does not solve problems that are not computable. In Computational Complexity, the complexity of a problem is characterized based on the amount of computational resources, such as space and time, needed to solve it. Problems that have the same complexity compose the same class. The computational complexity classes are related by a hierarchy. In Descriptive Complexity, a logic is used to express problems and capture computational complexity classes in order to express all and only the problems of this class. Thus, the complexity of a problem does not depend on physical factors, such as time and space, but only on the expressiveness of the logic that defines it. Important results of the area states that several classes of computational complexity can be characterized by a logic. For example, the class NP has been shown equivalent to the class of problems expressed by the existential fragment of Second-Order Logic. This close relationship between these areas allows some results about Logics to be transferred to Computational Complexity and vice versa. Despite of the importance of probabilistic algorithms and of Descriptive Complexity, there are few results on the characterization, by a logic, of probabilistic computational complexity classes. In this work, we show characterizations for each of the polinomial time probabilistic complexity classes. In our results, we use second-order generalized quantifiers to simulate the acceptance of the nondeterministic machines of these classes. We found Logical characterizations in the literature only for classes PP and BPP. In the first case, the logic employed was the first-order added by a quantifier most of second-order. With the approach established in this work, we obtain an alternative proof for the characterization of PP. With the same methodology, we also characterize the class &#8853;P through a logic with a second-order parity quantifier. In the case of BPP , there was a result that used a logic with probabilistic semantics. Using our approach of generalized quantifiers, we obtain an alternative characterization for this class. With the same method, we were able to characterize the probabilistic semantic classes RP, coRP, ZPP and the semantic class NP &#8745; coNP. Finally, we show an application of Descriptive Complexity results in the creation of algorithms from a logic specification.

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.

Em Complexidade Descritiva investigamos o uso de logicas para caracterizar classes problemas pelo vies da complexidade. Desde 1974, quando Fagin provou que NP e capturado pela logica existencial de segunda-ordem, considerado o primeiro resultado da area, outras relac~oes entre logicas e classes de complexidade foram estabelecidas. Os resultados mais conhecidos normalmemte envolvem logica de primeira-ordem e suas extens~oes, e classes de complexidade polinomiais em tempo ou espaco. Alguns exemplos sÃo que a logica de primeira-ordem estendida com o operador de menor ponto xo captura a clsse P e que a logica de segunda-ordem estendida com o operador de fecho transitivo captura a classe PSPACE. Nesta dissertaÃÃo, analisaremos inicialmente a expressividade de algumas logicas modais com relacÃo ao problema de decisÃo REACH e veremos que e possvel expressa-lo com as logicas temporais CTL e CTL. Analisaremos tambem o uso combinado de logicas de ordem superior com o operador de menor ponto xo e obteremos como resultado que cada nvel dessa hierarquia captura cada nvel da hierarquia determinstica em tempo exponencial. Como corolario, provamos que a hierarquia de HOi(LFP) nÃo colapsa, ou seja, HOi(LFP) HOi+1(LFP) / In Descriptive Complexity, we investigate the use of logics to characterize computational classes os problems through complexity. Since 1974, when Fagin proved that the class NP is captured by existential second-order logic, considered the rst result in this area, other relations between logics and complexity classes have been established. Wellknown results usually involve rst-order logic and its extensions, and complexity classes in polynomial time or space. Some examples are that the rst-order logic extended by the least xed-point operator captures the class P and the second-order logic extended by the transitive closure operator captures the class PSPACE. In this dissertation, we will initially analyze the expressive power of some modal logics with respect to the decision problem REACH and see that is possible to express it with temporal logics CTL and CTL. We will also analyze the combined use of higher-order logics extended by the least xed-point operator and obtain as result that each level of this hierarchy captures each level of the deterministic exponential time hierarchy. As a corollary, we will prove that the hierarchy of HOi(LFP), for i 2, does not collapse, that is, HOi(LFP) HOi+1(LFP)

Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-14T19:46:59Z No. of bitstreams: 1 2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-14T19:48:16Z (GMT) No. of bitstreams: 1 2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5) / Made available in DSpace on 2016-06-14T19:48:16Z (GMT). No. of bitstreams: 1 2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5) Previous issue date: 2010 / In Descriptive Complexity, we investigate the use of logics to characterize computational classes os problems through complexity. Since 1974, when Fagin proved that the class NP is captured by existential second-order logic, considered the rst result in this area, other relations between logics and complexity classes have been established. Wellknown results usually involve rst-order logic and its extensions, and complexity classes in polynomial time or space. Some examples are that the rst-order logic extended by the least xed-point operator captures the class P and the second-order logic extended by the transitive closure operator captures the class PSPACE. In this dissertation, we will initially analyze the expressive power of some modal logics with respect to the decision problem REACH and see that is possible to express it with temporal logics CTL and CTL . We will also analyze the combined use of higher-order logics extended by the least xed-point operator and obtain as result that each level of this hierarchy captures each level of the deterministic exponential time hierarchy. As a corollary, we will prove that the hierarchy of HOi(LFP), for i 2, does not collapse, that is, HOi(LFP) HOi+1(LFP) / Em Complexidade Descritiva investigamos o uso de logicas para caracterizar classes problemas pelo vies da complexidade. Desde 1974, quando Fagin provou que NP e capturado pela logica existencial de segunda-ordem, considerado o primeiro resultado da area, outras relac~oes entre logicas e classes de complexidade foram estabelecidas. Os resultados mais conhecidos normalmemte envolvem logica de primeira-ordem e suas extens~oes, e classes de complexidade polinomiais em tempo ou espaco. Alguns exemplos são que a l ogica de primeira-ordem estendida com o operador de menor ponto xo captura a clsse P e que a l ogica de segunda-ordem estendida com o operador de fecho transitivo captura a classe PSPACE. Nesta dissertação, analisaremos inicialmente a expressividade de algumas l ogicas modais com rela cão ao problema de decisão REACH e veremos que e poss vel express a-lo com as l ogicas temporais CTL e CTL . Analisaremos tamb em o uso combinado de l ogicas de ordem superior com o operador de menor ponto xo e obteremos como resultado que cada n vel dessa hierarquia captura cada n vel da hierarquia determin stica em tempo exponencial. Como corol ario, provamos que a hierarquia de HOi(LFP) não colapsa, ou seja, HOi(LFP) HOi+1(LFP) / FREIRE, Cibele Matos. Complexidade descritiva das lógicas de ordem superior com menor ponto fixo e análise de expressividade de algumas lógicas modais. 2010. 54 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2010.

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.

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.