Structures of bounded partition width

Blumensath, Achim; Grädel, Erich

doi:726

Structures of bounded partition width

Blumensath, Achim (Author)

2003

Verantwortlichkeitsangabevorgelegt von Achim Blumensath

ImpressumAachen : Publikationsserver der RWTH Aachen University 2003

UmfangX, 199 S.

Aachen, Techn. Hochsch., Diss., 2003

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grädel, Erich (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2003-11-04

Online
URN: urn:nbn:de:hbz:82-opus-7263
URL: https://publications.rwth-aachen.de/record/59169/files/Blumensath_Achim.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Graph (Genormte SW) ; Struktur (Genormte SW) ; Modelltheorie (Genormte SW) ; Komplexitätsmaß (Genormte SW) ; Informatik (frei) ; monadic second-order logic (frei) ; clique width (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
In der vorliegenden Dissertation wird die Fragestellung untersucht, welche monadischen Theorien einfach sind. Insbesondere werden entscheidbare Theorien betrachtet oder solche, die einfach genug sind, um Struktursätze zu entwickeln. Wir schlagen vor, die Trennlinie zwischen einfachen und komplizierten Theorien zu ziehen, indem wir eine Theorie genau dann einfach nennen, wenn sie in einem (evtl. unendlichen) gefärbten Baum interpretiert werden kann. Die so erhaltene Strukturklasse verallgemeinert die von Courcelle, Engelfriet und Rozenberg eingeführte Klasse der Graphen beschränkter Clique-Weite. In Anlehnung an deren Resultaten führen wir Terme ein, die beliebige relationale Strukturen bezeichnen, und wir zeigen, daß eine Struktur genau dann durch solch einen Term beschrieben werden kann, wenn sie in einem gefärbten Baum interpretierbar ist. Desweiteren erhalten wir eine Charakterisierung über hierarchische Zerlegungen der Struktur, welche wir dazu benutzen, ein Partitionsweite genanntes Komplexitätsmaß zu definieren, das den Begriff der Clique-Weite in geeigneter Weise verallgemeinert. Die Intuition, daß in Bäumen interpretierbare Strukturen eine einfache monadische Theorie besitzten, wird durch mehrere modelltheoretische Resultate gestützt. Endlichkeit der Partitionsweite bleibt unter elementaren Erweiterungen erhalten, und es existiert ein Kompaktheitssatz für Strukturen endlicher Partitionsweite. Desweiteren besitzen diese Strukturen nicht die Unabhängigkeitseigenschaft bzw. -- äquivalent dazu -- eine unbeschränkte VC-Dimension. Nachdem wir eine Klasse von einfachen Strukturen erhalten haben, drängt sich die Frage auf, ob diese Charakterisierung exakt ist, d. h., wir würden gerne wissen, ob alle anderen Strukturen eine komplizierte monadische Theorie besitzen. Wir vermuten, daß jede Struktur mit unbeschränter Partitionsweite beliebig große MSO-definierbare Gitter enthält. Dies würde bedeuten, daß die volle zweitstufige Theorie der Klasse aller endlichen Mengen in der monadischen Theorie einer solchen Struktur interpretiert werden kann. Insbesondere wäre die letztere also unentscheidbar. Ein Beweis würde somit die Vermutung von Seese beantworten, welche besagt, daß jeder Graph mit entscheidbarere MSO-Theorie eine endliche Clique-Weite besitzt. Unser Versuch einer Antwort auf diese Vermutung besteht aus einer Theorie von Zusammenhang, welche auf Schnitten und Separationen in Graphen beruht und die symmetrsich bezüglich Kanten und Nicht-Kanten ist. Nach mehreren technischen Vorbereitungen dieser Art sind wir in der Lage, den Kern des ursprünglichen Beweises von Robertson und Seymour zu ihrem Gittersatz vom Fall der Baumweite zur Partitionsweite zu übersetzen. Aber trotz dieser ermutigenden Resultate bleibt sowohl ein vollständiges Analogon zum Gittersatz, als auch die eigentliche Vermutung offen. Im zweiten Teil der Dissertation wenden wir uns einer Untersuchung von Teilklassen zu, welche aus Strukturen mit entscheidbarer monadische Theorie bestehen, die sich darüberhinaus endlich repräsentieren lassen. In erster Linie wird dies die Klasse aller Strukturen sein, welche im vollständigen binären Baum ohne zusätzliche Prädikate interpretiert werden können. Es werden algebraische Eigenschaften dieser Strukturen ermittelt. Insbesondere geben wir eine Charakterisierung aller linearen Ordnungen in dieser Klasse. Weiterhin zeigen wir, daß jede dieser Strukturen endlich in der bewachten Logik zweiter Stufe mit Kardinalitätquantoren axiomatisiert werden kann.

In the present thesis we study the question of which monadic theories are simple. In particular, we are looking for theories that are decidable or at least simple enough that we are able to derive structure theorems. We propose to draw the line between simple and complicated theories by defining that a structure has a simple monadic theory if and only if it can be interpreted in some (possibly infinite) coloured tree. The class of structures obtained this way generalises the class of graphs of bounded clique width which was originally defined by Courcelle, Engelfriet, and Rozenberg via graph grammars. Analogously to the results of Courcelle et.al., we will introduce terms denoting arbitrary relational structures and we show that a structure can be denoted by a term if and only if it is interpretable in some (possibly infinite) tree. Furthermore, we obtain an equivalent characterisation via hierarchical decompositions of the structure which can be used to define a complexity measure, called partition width, which provides our generalisation of the notion of clique width. The intuitive idea that structures interpretable in a tree have a simple monadic theory is supported by several model theoretic results we obtain for this class. Finiteness of partition width is preserved by elementary embeddings and we will prove a compactness theorem for structures of finite partition width. Furthermore, no such structure has the independence property or, equivalently, infinite VC-dimension, that is, in no structure of finite partition width it is possible to encode, in a first-order way, all subsets of some infinite set by single elements. After having obtained a class of simple structures the obvious next question is whether this characterisation is precise. That is, we would like to prove that all other structures have a complicated monadic theory. We conjecture that every structure of infinite partition width contains arbitrarily large finite MSO-definable grids. This would imply that the full second-order theory of the class of finite sets can be interpreted in the monadic second-order theory of every structure of infinite partition width. In particular, every such structure would have an undecidable MSO-theory. Therefore, a proof of this conjecture would settle the conjecture of Seese which states that every graph with decidable MSO-theory has finite clique width. We try to obtain an answer to this question by developing a theory of connectedness based on cuts and separations that is symmetric with regard to edges and non-edges. After sufficient preparations of this kind we are able to translate the core of the original proof of Robertson and Seymour's Excluded Grid Theorem from tree width to partition width. Despite these encouraging results, both, a full analogue of the Excluded Grid Theorem and the conjecture itself remain open. In the second part of the thesis we turn to the investigation of subclasses consisting of structures with decidable monadic theory that, furthermore, admit a finite representation. Mainly, we will consider the class of structures that can be interpreted in the complete binary tree without additional unary predicates. We will study algebraic properties of these structures including a characterisation of all linear orders contained in this class. We will also show that every such structure can be finitely axiomatised in guarded second-order logic with cardinality quantifiers.

OpenAccess:
PDF
(additional files)