Abstract
dc:descriptionIn 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.
Degree
thesis:*- Grantor dc:publisher
- Publikationsserver der RWTH Aachen University
- Year dc:date
- 2003
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Blumensath, Achim
- Contributors dc:contributor
-
- Grädel, Erich
Subjects
dc:subject × 8Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- eng
Identifiers
dc:identifier.*- OAI identifier oai:identifier
- oai:publications.rwth-aachen.de:59169