Achim Blumensath
email: blumensath@mathematik.tu-darmstadt.de

Bruno Courcelle
email: courcell@labri.fr

ON THE MONADIC SECOND-ORDER TRANSDUCTION HIERARCHY

Keywords: 1998 ACM Subject Classification: G.2.2 Graph Theory-Hypergraphs, F.4.1 Mathematical Logic-Model Theory Monadic Second-Order Logic, Guarded Second-Order Logic, Transductions, Hypergraphs

We compare classes of finite relational structures via monadic second-order transductions. More precisely, we study the preorder

for some transduction τ .

If we only consider classes of incidence structures we can completely describe the resulting hierarchy. It is linear of order type ω + 3. Each level can be characterised in terms of a suitable variant of tree-width. Canonical representatives of the various levels are: the class of all trees of height n, for each n ∈ N, of all paths, of all trees, and of all grids.

Introduction

Monadic second-order logic (MSO) is one of the most expressive logics for which the theories of many interesting classes of structures are still decidable. In particular, the infinite binary tree and many linear orders have a decidable MSO-theory [START_REF] Rabin | Decidability of second-order theories and automata on infinite trees[END_REF][START_REF] Shelah | The Monadic Second Order Theory of Order[END_REF] and the same holds for many classes of (finite or infinite) structures with bounded tree-width [START_REF] Blumensath | Logical Theories and Compatible Operations[END_REF][START_REF] Robertson | Graph Minors. V. Excluding a Planar Graph[END_REF]. Furthermore, for every fixed MSO-sentence ϕ and every class C of finite structures with bounded tree-width, there is a linear-time algorithm that checks whether a given structure from C satisfies ϕ [START_REF] Bodlaender | A linear time algorithm for finding tree-decompositions of small treewidth[END_REF][START_REF] Flum | Parametrized Complexity Theory[END_REF]. Examples of monadic second-order expressible graph properties are k-colourability, various types of connectivity, and planarity (via Kuratowski's well-known characterisation by forbidden configurations).

A variant of monadic second-order logic called guarded second-order logic (GSO) allows quantification not only over sets of elements but also over sets of edges (i.e., tuples from the relations) [START_REF] Grädel | Back and Forth Between Guarded and Modal Logics[END_REF]. The above mentioned linear-time algorithms can be adapted to this logic. There are tight links between guarded second-order logic and tree-width: every class of (finite or infinite) relational structures with a decidable GSO-theory has bounded tree-width. This gives a sort of converse to the above mentioned decidability results [START_REF] Seese | The structure of the models of decidable monadic theories of graphs[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs VIII: Orientations[END_REF]. The proof of this result uses a deep theorem of graph minor theory by Robertson and Seymour: a set of graphs has bounded tree-width if and only if it excludes some planar graph as a minor [START_REF] Robertson | Graph Minors. V. Excluding a Planar Graph[END_REF].

To compare the MSO-theories or GSO-theories of two classes of structures we can use monadic second-order transductions, a certain kind of interpretations suitable both, for monadic second-order logic and, using a detour via incidence structures, also for guarded second-order logic [START_REF] Blumensath | Logical Theories and Compatible Operations[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs V: On closing the gap between definability and recognizability[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs VIII: Orientations[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs XIV: Uniformly sparse graphs and edge set quantifications[END_REF].

In the present article we classify classes of finite structures according to their 'combinatorial complexity'. (Note that we do not consider decidability issues.) We will consider two ways to measure the complexity of such classes. On the one hand, we can use their tree-width and its variants. On the other hand, we can compare them via transductions. As it turns out, these two approaches are equivalent and they give rise to the same hierarchy. This indicates the robustness of our definitions and their intrinsic interest. Other possible hierarchies, based on different logics, will be briefly mentioned in Section 9.

Let us give more details. An MSO-transduction is a transformation of relational structures specified by monadic second-order formulae. As graphs can be represented by relational structures, we can use MSO-transductions as transformations between graphs. An MSO-transduction is a generalisation of the following kind of operations (see Definition 3.4):

(i) the definition of a relational structure "inside" another one (in model theory this is called an interpretation);

(ii) the replacement of a structure A by the union of a fixed number of disjoint copies of A, augmented with appropriate relations between the copies;

(iii) the expansion of a given structure A by a fixed number of unary predicates, called parameters. Usually, these predicates are arbitrary subsets of the domain, but we also may have a formula imposing restrictions on them.

Because of the possibility to use parameters, a transduction τ is a many-valued map in general. (We may also think of it as non-deterministic.) Each relational structure A has several images τ (A, P 1 , . . . , P n ) depending on the choice of the parameters P 1 , . . . , P n ⊆ A. If B = τ (A, P 1 , . . . , P n ) we can consider the tuple P 1 , . . . , P n as an encoding of B in A. The transduction τ is the corresponding decoding function.

Each transduction τ extends in a canonical way to a transformation between classes of structures. If C and K are classes of relational structures with C ⊆ τ (K), we can think of τ as a way of encoding the structures in C by elements of K. For instance, every finite graph can be encoded in a sufficiently large finite square grid (by a fixed transduction τ ). Every finite tree of height at most n (for fixed n) can be encoded in a sufficiently long finite path. But it is not the case that all finite trees can be encoded by paths (by a single transduction).

The purpose of this article is to classify classes of finite relational structures according to their encoding powers. We will compare classes C and K of structures by the following preorder:

C ⊑ K

: iff C ⊆ τ (K) for some MSO-transduction τ .

We attack the problem of determining the structure of this preorder. Since, at the moment, a complete description of this hierarchy seems to be out of reach, we concentrate on a variant where we replace monadic second-order logic by guarded second-order logic. In this case, the corresponding hierarchy can be described completely. To obtain a corresponding notion of transduction we cannot simply change the definition of an MSO-transduction to use GSOformulae since the resulting notion of transduction would not yield a reduction between GSO-theories, and it even would not be closed under composition. Instead, we will take a detour by combining ordinary MSO-transductions with a well-known translation between GSO and MSO. This translation is based on incidence structures. Let us first describe this notion for undirected graphs where it is very natural. There are two canonical ways to encode a graph G by a relational structure. We can use its adjacency representation which is a structure V, edg where the domain V consists of all vertices of G and edg is a binary relation containing all pairs of adjacent vertices. But we also can use the incidence representation of G. This is the structure V ∪ E, in where the domain V ∪ E contains both, the vertices and the edges of G, and in is the incidence relation between vertices and edges. In a similar way, we can associate with every relational structure A its incidence structure A in (see Definition 2.1) where the domain also contains elements for all tuples in some relation of A.

It is shown in [START_REF] Grädel | Back and Forth Between Guarded and Modal Logics[END_REF] that every GSO-formula ϕ talking about some structure A can be translated into an MSO-formula talking about the incidence structure A in , and vice versa. Hence, we can use incidence structures to obtain an analogue ⊑ in of the preorder ⊑ suitable for guarded second-order logic. We set

C ⊑ in K : iff C in ⊆ τ (K in ) for some MSO-transduction τ ,
where

C in := { A in | A ∈ C }.
The main result of the present article is a complete characterisation of the resulting hierarchy for classes of finite structures. We show that the preorder ⊑ in is linear of order type ω + 3. It turns out that every class of finite structures is equivalent to one of the following classes, listed in increasing order of generality:

• trees of height at most n, for each n ∈ N;

• paths;

• arbitrary trees (equivalently, binary trees); • (square) grids. Each of these levels can be characterised in terms of tree decompositions. Hence, we also obtain a corresponding hierarchy of complexity measures on structures that are compatible with MSO-transductions transforming incidence structures.

The upper levels of the hierarchy can be determined easily using techniques from graph minor theory developed by Robertson and Seymour, such as the notions of a minor and a tree decomposition. In particular, we employ two results characterising bounded tree-width and bounded path-width in terms of excluded minors [START_REF] Robertson | Graph Minors. I. Excluding a Forest[END_REF][START_REF] Robertson | Graph Minors. V. Excluding a Planar Graph[END_REF].

For the lower levels, which consist of classes of bounded path-width, the characterisation is more complicated and requires new results relating tree decompositions and monadic second-order logic.

In Sections 2 and 3 we give basic definitions. Section 4 collects some known results from graph minor theory. We also introduce a new variant of tree-width and prove some of its basic properties. In Section 5 we expound the connections between tree-width and monadic second-order transductions. In Section 6 we introduce the transduction hierarchy and we state our main theorem. Its proof is contained in Sections 7 and 8. In the first one, we prove that the hierarchy is strict while, in the second one, we show that it covers every class. The final Section 9 contains some extension of our results to other logics and some open problems in this direction.

Preliminaries

Let us fix our notation. We set [n] := {0, . . . , n -1} and we write P(X) for the power set of a set X. We denote tuples ā with a bar. The components of ā will be a 0 , . . . , a n-1 where the length n will usually be implicit. We sometimes identify a tuple ā with the set of its components. For instance, we write c ∈ ā to express that c = a i , for some i.

In this article all graphs, trees, and relational structures are finite. We will not repeat this finiteness assumption. A relational structure A is of the form A, R A 0 , . . . , R A m-1 with domain A and relations R A i . The signature of such a structure is the set Σ = {R 0 , . . . , R m-1 } of relation symbols. In some proofs we will also use signatures with constant symbols denoting elements of the domain. We write ar(R) for the arity of a relation R. For a signature Σ, we denote by STR[Σ] the class of all Σ-structures. We write A ⊕ B for the disjoint union of the structures A and B.

We mainly consider incidence structures. These are representations of structures A where we have added new elements to the domain, one for each tuple in the relations of A.

Definition 2.1. Let A = A, R A 0 , . . . , R A m-1 be a structure and let r be the maximal arity of a relation R i . The incidence structure of A is the structure

A in := A • ∪ E, P R 0 , . . . , P R m-1 , in 0 , . . . , in r-1 ,
where we extend the domain A by

E := R A 0 ∪ • • • ∪ R A m-1
, and the relations are

P R i := { c ∈ E | c ∈ R A i } , in i := { (a, c) ∈ A × E | |c| > i and a = c i } .

The class of all incidence structures is STR

in [Σ] := { A in | A ∈ STR[Σ] }.
Remark 2.2. Note that incidence structures are binary (i.e., their relations have arity at most 2). Hence, they can be regarded as bipartite labelled directed graphs.

One important property of incidence structures is the fact that they are sparse, i.e., their relations contain few tuples.

Definition 2.3. Let k ∈ N. A structure A = A, R is k-sparse 1 if, for every subset X ⊆ A and all relations R i , we have R i ∩ X ar(R i ) ≤ k • |X| . Lemma 2.4. Every incidence structure is 1-sparse.
Let us fix our notation regarding trees and graphs. Definition 2.5. A directed graph is a pair V, edg where V is the set of vertices and edg ⊆ V × V is the edge relation. Thus, graphs are by definition simple (without parallel edges). An undirected graph is a graph where the edge relation edg is symmetric. When speaking of a graph we will always mean an undirected one.

We regard a coloured graph as a relational structure V, E 0 , . . . , E k , P 0 , . . . , P m with binary relations E i and unary relations P i that encode the colours of, respectively, the edges and the vertices. We allow graphs whose edges and vertices have several colours. Trees play a major role in this article. Intuitively, a tree is a directed graph T with a unique vertex r of indegree 0, called the root of T, such that every vertex is reachable from r by a unique directed path. The actual definition we will use is slightly more concrete. It is based on the usual encoding of the vertices of a tree by finite sequences describing the path from the root to the given vertex. In fact, we introduce two notions of a tree: order-trees and successor-trees. The latter use the usual edge relation, while the former are equipped with the tree-order instead.

Definition 2.6. Let D be a set.

(a) For an ordinal α, we denote by D <α the set of all sequences of elements of D of length less than α. The prefix relation on D <ω is defined by

x y : iff y = xz , for some z ∈ D <ω .
The infimum of x and y with respect to , i.e., their longest common prefix, is denoted by x ⊓ y. (b) A finite prefix closed subset T ⊆ D <ω is called a tree domain. Following our intuition that a vertex is represented by the path leading to it, we call the empty sequence the root of T and the maximal elements of T its leaves. The domain of the complete m-ary tree of height n is m <n . Hence, m <0 is the empty tree, m <1 the one consisting only of the root, and m <2 consists of a root and m leaves.

Given a tree domain T we can define the successor relation edg on T by setting

x, y ∈ edg : iff y = xd for some d ∈ D .

In this case we call y a successor of x and x the predecessor of y. A structure of the form T, edg (and every structure isomorphic to it) is called a successor-tree. Sometimes it is convenient to replace the successor relation edg by the tree order . Structures of the form T, are called order-trees. A coloured tree is the expansion of a (order-or successor-) tree by unary predicates P . (We do not require these predicates to be pairwise disjoint. Hence, every vertex may have none, one, or several colours.) We write TREE m for the class of all order-trees T, , P 0 , . . . , P m-1 with m colours. The set of leaves of a tree T is denoted by Lf(T).

(c) Let T = T, be an order-tree. The level of an element v ∈ T is the number of vertices u ∈ T with u ≺ v. We denote it by |v|. The height of T is the least ordinal α greater than the level of every element of T . Hence, the empty tree has height 0 and the tree with a single vertex has height 1. The out-degree of T is the maximal number of successors of a vertex of T. For successor-trees we define these notions analogously.

(d) Let T be a tree and v a vertex of T. The subtree of T rooted at v is the subtree T v consisting of all vertices u with v u, i.e., all vertices below v.

Sometimes it is possible to reduce statements about relational structures to statements about graphs. One way to do so consists in replacing a structure by its Gaifman graph.

Definition 2.7. The Gaifman graph of a structure A = A, R is the undirected graph Gf(A) := A, edg , with the same domain A and with the edge relation

edg := { (u, v) | u = v and there is some c ∈ R A i with u, v ∈ c } .

Monadic second-order logic and transductions

Monadic second-order logic (MSO) is the extension of first-order logic by set variables and quantifiers over such variables. An important variant of MSO is guarded second-order logic (GSO) where one can quantify not only over sets of elements but also over sets of tuples from the relations (see [START_REF] Grädel | Back and Forth Between Guarded and Modal Logics[END_REF] for details). Hence, guarded second-order logic over a given structure A is equivalent to monadic second-order logic over its incidence structure A in .

Lemma 3.1 ([GHO02]). (a) For every GSO-sentence ϕ, we can effectively construct an MSO-sentence ψ such that

A |= ϕ iff A in |= ψ , for all structures A .
(b) For every MSO-sentence ϕ, we can effectively construct a GSO-sentence ψ such that

A in |= ϕ iff A |= ψ , for all structures A .
Throughout the article we will consistently work with incidence structures, thereby avoiding the treatment of guarded second-order logic. In particular, all formulae are tacitly assumed to be MSO-formulae.

Besides MSO and GSO we also consider their counting extensions CMSO and CGSO. These add predicates of the form |X| ≡ k (mod m) to, respectively, MSO and GSO, where X is a set variable and k, m are numbers. All of our results for GSO go through also for CGSO, i.e., for CMSO-transductions between incidence structures. In Section 9 we will give a partial characterisation of the hierarchy for CMSO-transductions of graphs (not of incidence graphs). In this case the availability of counting predicates does make a difference.

To state the composition theorem below it is of advantage to work with a variant of MSO without first-order variables. This variant has atomic formulae of the form X ⊆ Y and R Z, for set variables X, Y, Z 0 , Z 1 , . . . , where a formula of the form R Z states that there are elements a i ∈ Z i such that the tuple ā is in R. Note that every general monadic second-order formula with first-order variables can be brought into this restricted form by replacing all first-order variables by set variables and adding the condition that these sets are singletons.

Whenever we speak of MSO we will have this version in mind. In particular, the following definition of the rank of a formula is based on this variant. When writing down concrete formulae, on the other hand, we will allow the use of first-order variables to improve readability. We regard every such formula as an abbreviation of a formula of the restricted form. Similarly, when we use structures with constants we actually regard each constant as a singleton set.

Definition 3.2. (a) The rank qr(ϕ) of a formula ϕ is the nesting depth of quantifiers in ϕ. Formulae of rank 0 are called quantifier-free.

(b) The monadic theory of rank m of a structure A is

MTh m (A) := { ϕ ∈ MSO | A |= ϕ, qr(ϕ) ≤ m } .
For a tuple ā of elements of A, we also consider the monadic theory MTh m (A, ā) of the expansion A, ā .

Remark 3.3. We use the term 'rank' instead of the more natural 'quantifier rank' since in Section 9 below we will consider CMSO where the notion of rank has to be adapted for our results to go through.

In order to compare the monadic theories of two classes of structures we employ MSOtransductions. To simplify the definition we introduce three simple operations and we obtain MSO-transductions as compositions of these. Definition 3.4. (a) Let k ≥ 2 be a natural number. The operation copy k maps a structure A to the expansion

copy k (A) := A ⊕ • • • ⊕ A, ∼, P 0 , . . . , P k-1
of the disjoint union of k copies of A by the following relations. Denoting the copy of an element a ∈ A in the i-th component of A ⊕ • • • ⊕ A by the pair a, i , we define

P i := { a, i | a ∈ A } and a, i ∼ b, j : iff a = b .
For k = 1, we set copy 1 (A) := A.

(b) For m ∈ N, we define the operation exp m that maps a structure A to all possible expansions by m unary predicates Q 0 , . . . , Q m-1 ⊆ A. Note that this operation is manyvalued and that exp 0 is just the identity.

(c) A basic MSO-transduction is a partial operation τ on relational structures described by a list χ, δ(x), ϕ 0 (x), . . . , ϕ s-1 (x) of MSO-formulae called the definition scheme of τ . Given a structure A that satisfies the formula χ the operation τ produces the structure

τ (A) := D, R 0 , . . . , R s-1
where

D := { a ∈ A | A |= δ(a) } and R i := { ā ∈ D ar(R i ) | A |= ϕ i (ā) } . If A |= χ then τ (A) remains undefined.
(d) A k-copying MSO-transduction τ is a (many-valued) operation on relational structures of the form τ 0 • copy k • exp m where τ 0 is a basic MSO-transduction. When the value of k does not matter, we will simply speak of a transduction.

Note that, due to exp m , a structure can be mapped to several structures by a transduction. Consequently, we consider τ (A) as the set of possible values (τ 0 • copy k )(A, P ) where P ranges over all m-tuples of subsets of A.

For a class C, we set

τ (C) := { τ (A) | A ∈ C } . Remark 3.5. (a)
The expansion by m unary predicates corresponds, in the terminology of [START_REF] Courcelle | The monadic second-order logic of graphs VIII: Orientations[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs XIV: Uniformly sparse graphs and edge set quantifications[END_REF], to using m parameters. We will use this terminology, for instance, in the proof of Theorem 5.5. (b) Note that every basic MSO-transduction is a 1-copying MSO-transduction without parameters.

Example 3.6. (a) Let Σ be a signature and let r be the maximal arity of a relation in Σ.

The operation mapping an incidence structure

A in ∈ STR in [Σ] to the structure Gf(A) in is a k-copying MSO-transduction
where k = r(r -1)/2, for r ≥ 2, and k = 1, for r ≤ 1.

(b) For every fixed number n ∈ N, we describe a transduction τ transforming a path P of length l into the class of all trees of height n with l + 1 vertices.

We can encode a tree T of height n with m vertices as a finite word w of length m over the alphabet [n] as follows. Let v 0 < lex • • • < lex v m-1 be the enumeration of the vertices of T in lexicographic order, and let l i be the level of v i . We encode T by the word w := l 0 . . . l m-1 . A transduction can recover T from w as follows. Each position in w corresponds to a vertex. The predecessor of the i-th vertex v is the maximal vertex to the left of v whose label is less than l i . Clearly, this predecessor relation is definable in monadic second-order logic.

The two most important properties of MSO-transductions are summarised in the following lemmas.

Lemma 3.7. Let τ be a transduction. For every MSO-sentence ϕ, there exists an MSOsentence ϕ τ such that, for all structures A,

A |= ϕ τ iff B |= ϕ for some B ∈ τ (A) .
Furthermore, if τ is quantifier-free, then the rank of ϕ τ is no larger than that of ϕ.

Corollary 3.8. For every quantifier-free transduction τ and every m ∈ N, there exists a function f τ on monadic theories of rank m such that

MTh m (τ (A)) = f τ MTh m (A) , for all structures A . Lemma 3.9 ([Cou91]
). For all transductions σ, τ there exists a transduction ̺ such that ̺ = σ • τ .

As a further example note that we can use transductions to translate between order-trees and successor-trees.

Lemma 3.10. (a) There exists a transduction τ mapping an order-tree to the corresponding successor-tree.

(b) There exists a transduction σ mapping a successor-tree to the corresponding ordertree.

Similarly there are transductions translating between a structure and its incidence structure.

Lemma 3.11. For every signature Σ, there exists a transduction τ such that τ

(A in ) = A, for all A ∈ STR[Σ].
The converse statement is a much deeper result and requires the structure in question to be k-sparse for some fixed k.

Theorem 3.12 ([Cou03, Blu10]). For every signature Σ and all numbers k ∈ N, there exists an MSO-transduction τ such that τ

(A) = A in , for all k-sparse structures A ∈ STR[Σ].
We have seen in Lemma 3.7 that transductions relate the monadic theories of two structures. We also need techniques to relate the monadic theory of a structure to those of its substructures. The disjoint union operation can frequently be used for this purpose (for a proof of the following theorem see, e.g., Theorem 7.11 of [START_REF] Libkin | Elements of Finite Model Theory[END_REF], or [START_REF] Courcelle | An axiomatic definition of context-free rewriting and its application to NLC graph grammars[END_REF]).

Theorem 3.13. Let Σ and Γ be relational signatures with constants. For every m ∈ N, there exists a (computable) binary operation ⊕ m on monadic theories of rank m such that

MTh m (A ⊕ B) = MTh m (A) ⊕ m MTh m (B) ,
for all Σ-structures A and Γ -structures B.

Below we will mainly make use of the following corollary.

Lemma 3.14. Let T be an order-tree and v ∈ T a vertex. Suppose that T ′ is the order-tree obtained from T by replacing the subtree T v by some tree S. Let c be a tuple of vertices of T with v c i , for all i. If ā are vertices of T v and b are vertices of S such that

MTh m (T v , ā) = MTh m (S, b) then it follows that MTh m (T, āc) = MTh m (T ′ , bc) .
Proof Let C be the tree obtained from T by replacing the subtree T v by a single vertex w. We define the following auxiliary predicates: andQ ′ 1 := S . We construct a quantifier-free transduction τ such that

P := {w} , Q 0 := { x ∈ C | x ≺ w } , Q 1 := T v ,
τ C, P, Q 0 , c ⊕ T v , Q 1 , ā = T, āc , τ C, P, Q 0 , c ⊕ S, Q ′ 1 , b = T ′ , bc . If f τ
is the function from Corollary 3.8 and ⊕ m the operation from Theorem 3.13, it follows that

MTh m (T ′ , bc) = f τ MTh m (C, P, Q 0 , c) ⊕ m MTh m (S, Q ′ 1 , b) = f τ MTh m (C, P, Q 0 , c) ⊕ m MTh m (T v , Q 1 , ā) = MTh m (T, āc) , as desired.
Hence, it remains to define τ . Let { , P, Q 0 , d} be the signature of C, P, Q 0 , c , and

{ , Q 1 , ē} the signature of T v , Q 1 , ā and S, Q ′ 1 , b .
For τ we can use the basic MSOtransduction consisting of the following formulae:

χ := true , δ(x) := ¬P x , ϕ (x, y) := x y ∨ (Q 0 x ∧ Q 1 y) .

Minors and tree decompositions

Some properties of the transduction hierarchy, which we will introduce in Section 6 below, can be deduced from results about graph minors. (b) A minor of a graph G is a graph that can be obtained from G by first deleting some vertices and edges and then contracting some of the remaining edges. For a class C of graphs, we denote by Min(C) the class of all minors of graphs in C.

One central tool in graph minor theory is the notion of a tree decomposition and the related complexity measures called tree-width and path-width. These notions extend in a natural way to relational structures. Definition 4.2. Let A = A, R be a structure.

(a) A tree decomposition of A is a family D = (U v ) v∈T of (possibly empty) subsets U v ⊆ A indexed by a rooted tree T such that

• for every element a ∈ A, the set { v ∈ T | a ∈ U v } is nonempty and connected in T ;

• for every tuple c ∈ R i , there is some index v ∈ T with c ⊆ U v . We call the sets U v the components of the decomposition, and T is its underlying tree.

The height of a tree decomposition D = (U v ) v∈T is the height of T , while its width is the number

wd(D) := sup v∈T (|U v | -1) .
(b) The tree-width twd(A) of A is the minimal width of a tree decomposition of A. (c) The path-width pwd(A) of A is the minimal width of a tree decomposition of A where the underlying tree is a path.

(d) The n-depth tree-width twd n (A) of A is the minimal width of a tree decomposition of A whose underlying tree has height at most n.

(e) For a class C of structures, we define twd(C) as the supremum of twd(A), for A ∈ C, and similarly for pwd(C) and twd n (C).

Remark 4.3. (a) The n-depth tree-width of a graph G is related to its tree-depth td(G) as introduced by Nešetřil and Ossona de Mendez [START_REF] Nešetřil | Linear time low tree-width partitions and algorithmic consequences[END_REF][START_REF] Nešetřil | Tree-depth, subgraph coloring and homomorphism bounds[END_REF]. The tree-depth of a graph G is the least number n such that some orientation of G is a subgraph of some order-tree of height n. For a graph G, it follows that

• td(G) ≤ n implies twd n (G) < n;

• twd n (G) < k implies td(G) ≤ nk. These facts are easy to establish. We will not need them in the following.

(b) There are some simple relations between n-depth tree-width, path-width, and treewidth. For every graph G, we have (Let us sketch the proof of the last inequality: let (U v ) v∈T be a tree decomposition of G of height n and width twd n (G). As the components of a path decomposition of G we take all sets of the form

twd(G) ≤ twd n+1 (G) ≤ twd n (G) , for every n ∈ N ,
U v 0 ∪ • • • ∪ U v k , where v 0 . . . v k is a path from the root v 0 to some leaf v k of T .)
The next lemma shows that most questions regarding tree decompositions of a structure can be reduced to the corresponding questions about its Gaifman graph. For many of the following results it is therefore sufficient to consider graphs. Lemma 4.4. Let A be a structure. A family (U v ) v∈T is a tree decomposition of A if and only if it is a tree decomposition of Gf(A).

Proof (⇒) is immediate. (⇐) follows from the fact that every tree decomposition of a clique has one component U v containing the whole clique. This implies that, for every clique C in Gf(A) induced by some tuple c ∈ R i , there is some vertex v ∈ T with C ⊆ U v . Hence, every tuple c ∈ R i is contained in some component U v .

In order to separate the higher classes of the hierarchy, we shall employ two deep results of Robertson and Seymour about excluded minors.

Theorem 4.5 (Excluded Tree Theorem [START_REF] Robertson | Graph Minors. I. Excluding a Forest[END_REF]). For each tree T, there exists a number k ∈ N such that We also need a variant of these theorems for n-depth tree-width. The next lemma contains the main technical argument. Lemma 4.8. Suppose that G is a graph that does not contain a path of length l. Then G has a tree decomposition of height at most l and width at most l -1.

T / ∈ Min(G) implies pwd(G) < k ,
Proof Let T, be a depth-first spanning order-tree of G, i.e., a spanning tree such that, for every edge (u, v) of G we have u v or v u (for details see, e.g., [START_REF] Diestel | Graph Theory[END_REF] where such spanning trees are called normal ). We define a tree decomposition (U v ) v∈T of G by setting

U v := { u ∈ T | u v } .
Since T is depth-first, it follows that every edge (u, v) of G is contained in some component U w where w is the maximum of u and v.

The height of the tree T can be at most l since G contains no path of length l. Furthermore, we have |U v | = |v| + 1 ≤ l. Hence, the width of the tree decomposition is at most l -1. Theorem 4.9 (Excluded Path Theorem). For each path P, there exist numbers n, k ∈ N such that

P / ∈ Min(G) implies twd n (G) < k ,
for every graph G .

Proof Suppose that P / ∈ Min(G) and let l be the length of P. Then the preceding lemma implies that twd l (G) < l.

Corollary 4.10. (a) A class of graphs has bounded n-depth tree-width, for some n, if and only if it excludes some path as a minor (equivalently, as a subgraph).

(b) A class of graphs has bounded tree-depth if and only if it excludes some path as a minor (equivalently, as a subgraph).

We can also compute a bound on the n-depth tree-width in terms of the (n + 1)-depth tree-width. It will be needed in the proof of Theorem 8.2 below.

We say that the tree S, can be embedded into a tree T, if there exists an orderpreserving injective mapping S, → T, , i.e., if S, , regarded as relational structure, is isomorphic to an induced substructure of T, . For instance, we have an embedding as indicated by the labels. If S can be embedded in T then S is isomorphic to a minor of T , when we consider S and T as graphs.

Definition 4.11. Let D = (U v ) v∈T be a tree decomposition and let F be a set of edges of (the successor-tree corresponding to) T . The tree decomposition D/F obtained by contracting the edges in F is

D/F := (U ′ [v] ) [v]∈T /F , where U ′ [v] := u∈[v] U u . Lemma 4.
12. Let G be a graph and let D := (U v ) v∈T be a tree decomposition of G of width k and height at most n + 1. If m ∈ N is some number such that the tree m <n+1 cannot be embedded into T , then twd n (G) < m(k + 1).

Proof We construct a tree decomposition D ′ of height at most n and width at most m(k+1)-1 as follows. Let P ⊆ T be the minimal (w.r.t. ⊆) set of vertices that contains

• every leaf of T at level n and • every vertex that has at least m successors in P . Since m <n+1 cannot be embedded into T it follows that P does not contain the root of T . Let F be the set of all edges of T linking a vertex in T P to a vertex in P . By definition of P it follows that (i) every vertex of T has less than m F -successors; (ii) every path of T from the root to some leaf on level n contains at least one edge from F ; and (iii) no such path contains two consecutive edges from F .

The decomposition D ′ := D/F obtained by contracting all edges in F has width at most

k + 1 + (m -1)(k + 1) -1 < m(k + 1) .
Furthermore, the height of the underlying tree is at most n.

Corollary 4.13. Let C be a class such that k := twd n+1 (C) < ∞ and let m ∈ N. If every structure A ∈ C has a tree decomposition (U v ) v∈T of width k and height at most n + 1 such that the tree m <n+1 cannot be embedded into T , then twd n (C) < m(k + 1) < ∞.

We conclude this section with a lemma that will be useful when constructing transductions τ n that transform a structure into their tree decompositions of height n. Our construction works for all tree decompositions that are strict in the following sense.

= min { v ∈ T | a ∈ U v } .
Note that µ(a) is well-defined since, by the definition of a tree decomposition, there is at least one v ∈ T such that a ∈ U v . (b) For v ∈ T , we set

U ⇑v := u v U u u≺v U u . (c) The tree decomposition (U v ) v is strict if, for every v ∈ T , • U v ∩ µ(A) = ∅ (equivalently, U v U u = ∅,
where u is the predecessor of v) and • if v is not the root of T , then the subgraph of Gf(A) induced by the set U ⇑v is connected.

We conclude this section by a result implying that, for our purposes, it will be sufficient to consider only strict tree decompositions.

Lemma 4.15. Let G be a graph. For every tree decomposition (U v ) v∈T of G, there exists a strict tree decomposition (U ′ v ) v∈T ′ of G whose width and height are at most those of (U v ) v∈T . Proof By induction on n ∈ N, we will construct a sequence (U n v ) v∈T n of tree decompositions such that U n ⇑v is connected, for every v ∈ T n with level 0 < |v| ≤ n. (Recall that |v| denotes the level of v, and the root is the only vertex of level 0.) Furthermore, the restriction of T n to the set of vertices of level at most n will coincide with the corresponding restriction of T n+1 , and we have

U n+1 v = U n
v , for all v ∈ T n+1 with level |v| ≤ n. It will follow that the sequence has a limit (U ω v ) v∈T ω where

T ω := n∈N { v ∈ T n | |v| ≤ n } and U ω v := U |v| v .
We start the construction with T 0 := T and U 0 v := U v . Suppose that we have already defined (U n v ) v∈T n . For every vertex v ∈ T n of level |v| = n + 1 we modify the tree decomposition as follows. Let C 0 , . . . , C m-1 be an enumeration of the connected components of U n ⇑v . We replace in T n the subtree rooted at v by m copies S 0 , . . . , S m-1 of the subtree, all attached to the predecessor of v. For u ∈ S i we define U n+1 u := U n u ∩ C i . We can do these modifications for all vertices of level n + 1 simultaneously. Let (U n+1 v ) v∈T n+1 be the resulting tree decomposition.

The limit (U ω v ) v∈T ω of this sequence satisfies the connectedness requirement of a strict tree decomposition. To also satisfy the other condition we proceed as follows. Let F be the set of all edges (u, v) of T ω such that U v ∩ µ(V ) = ∅. (Note that this implies U v ⊆ U u .) We construct the tree decomposition (U ′ v ) v∈T ′ by contracting all edges in F . The details and the remaining verifications are left to the reader.

Tree decompositions and transductions

In this section we relate the material presented in the preceding one to monadic secondorder transductions. Let us start by showing that there is a transduction computing the minors of a graph.

Lemma 5.1 ([Cou95]

). There exists a transduction τ such that τ (G in ) = Min(G), for every graph G.

Proof A minor H of G is obtained by deleting vertices, deleting edges, and contracting edges. Hence, we can encode H by four sets: the set of vertices we delete, the set of edges we delete, the set of edges we contract, and a set of vertices containing one representative of each contracted subgraph of G (these vertices serve as vertices of the resulting graph H). With the help of these parameters we can define H inside of G in by MSO-formulae.

There is a close relationship between tree decompositions and transductions.

Lemma 5.2. For every signature Σ and every number k ∈ N, there exists a transduction τ k : TREE 0 → STR in [Σ] that maps an order-tree T to the class of all incidence structures in such that the corresponding Σ-structure A has a tree decomposition of width at most k with underlying tree T .

Proof Suppose that A is a structure which has a tree decomposition (U v ) v∈T of width k. We prove that A can be defined from a colouring of T where the number of colours depends only on Σ and k.

Let C 0 , . . . , C m-1 be an enumeration of all Σ-structures whose domain is a subset of [k + 1]. For each v ∈ T , let U v be the substructure of A induced by U v . It follows that, for every v ∈ T , we can find some index λ(v) such that

U v ∼ = C λ(v) . Let π v : U v → C λ(v) be the corresponding isomorphism.
Furthermore, we associate with each edge (u, v) of T the binary relation

R(u, v) := { (π u (a), π v (a)) | a ∈ U u ∩ U v } ⊆ [k + 1] × [k + 1] .
We can recover A from T with the help of the vertex colouring λ and the edge colouring R. We form the disjoint union of all structures (C λ(v) ) in , for v ∈ T , and we identify two elements i ∈ C λ(u) and j ∈ C λ(v) if (u, v) is an edge of T such that (i, j) ∈ R(u, v). This can be performed by an n-copying MSO-transduction where n is the maximal size of the structures

(C i ) in , i < m.
We have just seen that we can map a class of trees to a class of structures with these trees as tree decompositions. Conversely, if we only consider strict tree decompositions, we can define a transduction mapping a class of structures to the corresponding class of trees. Recall the function µ : A → T from Definition 4.14. that assigns to an element a ∈ A the minimal index v ∈ T such that a ∈ U v .

Proposition 5.3. For each number n ∈ N, there exists an MSO-formula ϕ n (x, y; Z) such that, for every strict tree decomposition D = (U v ) v∈T of a graph G of height at most n, there are sets L 0 , . . . , L n-1 ⊆ V such that

G |= ϕ n (a, b; L) iff µ(a) ≤ µ(b) .
Proof Given D we use the sets

L i := { a ∈ V | |µ(a)| = i }
of all elements that first appear at level i of the tree. In particular, L 0 = U is the root component of the tree decomposition. For k < n, let G ≥k be the subgraph of G induced by Theorem 5.4. For each constant n ∈ N, there exists a transduction τ n mapping a graph G to the class of all (underlying trees of ) strict tree decompositions of G of height at most n.

L k ∪ • • • ∪ L n-1 . For a ∈ L i
Proof Let D = (U v ) v∈T be a strict tree decomposition of G, and let ϕ n (x, y; L) be the formula from Proposition 5.3 with parameters L 0 , . . . , L n-1 ⊆ V . We can define the tree T underlying D as follows:

• Its root is any element of L 0 = U .

• For the other vertices of T , we choose one vertex in each ∼-class different from L 0 . Note that ∼ is definable with the help of ϕ n . • The ordering of T is defined by ϕ n . Hence, we obtain a transduction with parameters L that transforms a graph into a 'candidate' tree decomposition. Via a backwards translation we can write down a formula stating that the candidate given by the parameters L corresponds to an actual strict tree decomposition. We omit the details which are standard for this type of construction.

In Lemma 5.2 we have seen how to obtain classes of bounded tree-width from classes of trees. Conversely, it is the case that every class obtained from a class of trees via a transduction has a bounded tree-width.

Theorem 5.5. For every transduction τ : TREE m → STR in [Σ], there exists a number k ∈ N such that, for each m-coloured tree T with image A in ∈ τ (T), the structure A has a tree decomposition of width at most k where the underlying tree is T.

Remark 5.6. (a) Courcelle and Engelfriet [START_REF] Courcelle | A Logical Characterization of the Sets of Hypergraphs Defined by Hyperedge Replacement Grammars[END_REF] have shown that an incidence structure A in obtained via a transduction τ from an m-coloured tree T has bounded tree-width. Theorem 5.5 strengthens this result by proving that, if A in is the image of a tree T, then we can use the same tree T as the tree underlying a tree decomposition of the given width.

(b) Lapoire has announced in [START_REF] Lapoire | Recognizability Equals Monadic Second-Order Definability for Sets of Graphs of Bounded Tree-Width[END_REF] a result somewhat related to Theorem 5.4. He claims that, for every k ∈ N, there exists a transduction that transforms a given graph G of tree-width at most k to a coloured tree (like in the proof of Lemma 5.2) that encodes some tree decomposition of G of width at most k. Our result is less ambitious in the sense that we only consider tree decompositions of a fixed height. This enables us to give a precise description of which tree decompositions (the strict ones) our transduction returns. Note that one can show that, for k ≥ 2, there is no such transduction that would return all tree decompositions of G of width at most k.

We split the proof into several lemmas. As a technical tool we introduce a second kind of hierarchical decompositions of structures and a corresponding notion of width. To simplify the definition we will only consider incidence structures.

Definition 5.7. Let A in = A ∪ E, P , in 0 , . . . be an incidence structure.

(a) A partition refinement of A in is a family Π = (W v , ≈ v ) v∈T of pairs consisting of a subset W v ⊆ A ∪ E and an equivalence relation ≈ v on W v with the following properties:

• The index set T is a tree.

• For the root , we have W = A ∪ E • For every internal vertex (i.e., non-leaf) u ∈ T with successors v 0 , . . . , v n-1 , sets

W v 0 , . . . , W v n-1 form a partition of W u . • |W u | = 1, for every leaf u ∈ T . • x ≈ v y and u v implies x ≈ u y.
• If u is an internal vertex of T , v, w successors of u, not necessarily distinct, and

x ∈ W v , y ∈ W w elements, then x ≈ u y implies either

x, y ∈ A and, for every e ∈ E (W v ∪ W w ) and every i ,

(x, e) ∈ in i ⇔ (y, e) ∈ in i or
x, y ∈ E and, for every a ∈ A (W v ∪ W w ) and every i ,

(a, x) ∈ in i ⇔ (a, y) ∈ in i .
Note that it follows that, for every element x ∈ A ∪ E, there is some leaf u ∈ T such that

W u = {x}. (b)
The width of a partition refinement Π = (W v , ≈ v ) v∈T is the maximum number of equivalence classes realised in some component W v :

wd(Π) := max v∈T |W v /≈ v | .
The partition-width of the structure A in is the minimal width of a partition refinement of A in .

The notion of a partition refinement and of partition-width are adaptations of definitions from [START_REF] Blumensath | A Model Theoretic Characterisation of Clique-Width[END_REF][START_REF] Blumensath | Structures of Bounded Partition Width[END_REF]. Up to a factor of 2, the partition-width of an incidence structure and its clique-width coincide. Lemma 5.9. For every partition refinement Π = (W v , ≈ v ) v∈T of an incidence structure A in = A ∪ E, P , in 0 , . . . , in r-1 , there exists a tree decomposition D = (U v ) v∈T of A with the same underlying tree T such that wd(D) < (r + 3) • wd(Π) .

Its incidence structure is

A in = A ∪ E, P R , in 0 , in 1 , in 2 with E = {x,
Proof Let l : A ∪ E → Lf(T ) be the function assigning to every x ∈ A ∪ E the unique leaf l(x) of T such that W l(x) = {x}. We claim that the desired tree decomposition (U u ) u∈T of A is given by

U u := B u ∪ C u ∪ D u
where

B u := { v ∈ A | u l(v)
and (v, e) ∈ in i for some i < r and e ∈ E with u l(e) } ,

C u := { v ∈ A | u l(v)
and (v, e) ∈ in i for some i < r and e ∈ E with u l(e) } ,

D u := { v ∈ A | (v, e) ∈ in i for some i < r and e ∈ E with l(v) ⊓ l(e) = u } .
Note that the connectedness condition holds since (v, e) ∈ in i implies that v belongs to precisely those components U u such that u lies on the path from l(v) to l(e).

It remains to prove that

|U u | ≤ (r + 3) • wd Π. If u = l(c), for some c ∈ E, then U u = C u consists of the components of c. Hence, |U u | = |c| ≤ r. Therefore, we may assume that u / ∈ l[E]. Let [x] u := { y ∈ W u | y ≈ u x }
denote the ≈ u -class of x. We prove the following bounds.

(1)

|[x] u | = 1, for all x ∈ B u . (2) |[x] u ∩ U u | ≤ 2, for all x ∈ D u . (3) |C u | ≤ r • |W u /≈ u |. Since B u , D u ⊆ W u it then follows that |U u | = |B u ∪ C u ∪ D u | ≤ (r + 3) • |W u /≈ u |.
(1) Let x ∈ B u . There is some tuple e ∈ E and some index i such that (x, e) ∈ in i and u l(e). We have (y, e) ∈ in i , for every y ∈ W u such that y ≈ u x. Since x is the only such element it follows that [x] u = {x}.

(2) Let x ∈ D u . There is some tuple e ∈ E and some i such that (x, e) ∈ in i and u = l(x) ⊓ l(e). Let v be the successor of u such that v l(e). We have (y, e) ∈ in i , for all

y ∈ W u W v such that y ≈ u x. Hence, [x] u W v = {x}.
Suppose that there is some element y

∈ [x] u ∩ W v ∩ U u .
By definition of U u there is some tuple f ∈ E and some j such that (y, f ) ∈ in j and l(y) ⊓ l(f ) u. As above it follows that

[x] u ∩ W v = {y}. Consequently, we have |[x] u ∩ U u | ≤ 2.
(3) Let x ∈ C u and consider some tuple e ∈ E such that (x, e) ∈ in i and u l(e). Set Lemma 5.10. Let τ : TREE m → STR in [Σ] be a basic MSO-transduction such that, for every m-coloured order-tree T with image A in ∈ τ (T), we have

A ∪ E = Lf(T) and A ∩ E = ∅ .
Then there exists a number n ∈ N such that, for every order-tree T, we can find a partition refinement (W v , ≈ v ) v∈T of τ (T) of width at most n.

Proof Let χ, δ(x), (ϕ P R (x)) R , (ϕ in i (x, y)) i<r be the definition scheme of τ , and let h be the maximal rank of these formulae. Given T we define the desired partition refinement Π = (W u , ≈ u ) u∈T by setting

W u := { x ∈ Lf(T ) | u x } , and x ≈ u y : iff MTh h (T v , x) = MTh h (T w , y) ,
where v, w are the successors of u with x ∈ W v and y ∈ W w .

(If u is a leaf of T then W u = {x} and we take the equality relation for ≈ u .) Note that the index of ≈ v is finite and that it only depends on h and not on the input tree T.

It remains to show that Π is actually a partition refinement. First, let us prove that x ≈ v y and u v implies x ≈ u y. It is sufficient to consider the case that u is the predecessor of v. Then the general case follows by induction. Hence, suppose that v is a successor of u, that w, w ′ are successors of v, and that x, y are leaves with w

x and w ′ y such that x ≈ v y. Then we have

MTh h (T w , x) = MTh h (T w ′ , y) ,
which, by Lemma 3.14, implies that

MTh h (T v , x) = MTh h (T v , y) .
Consequently, we have x ≈ u y.

We also have to show that the incidence relation is invariant under ≈ u . Let v, w be successors of u and suppose that x, y are leaves with v x and w y such that x ≈ u y. We distinguish two cases.

Suppose that x, y ∈ A and let e ∈ E (W v ∪ W w ) be an edge. Since

MTh h (T v , x) = MTh h (T w , y) , it follows that T |= ϕ in i (x, e) iff T |= ϕ in i (y, e) .
Hence, (x, e) ∈ in i iff (y, e) ∈ in i . Now, suppose that x, y ∈ E and let z ∈ A (W v ∪ W w ) be an element. Since

MTh h (T v , x) = MTh h (T w , y) , it follows that T |= ϕ in i (z, x) iff T |= ϕ in i (z, y) .
Hence, (z, x) ∈ in i iff (z, y) ∈ in i .

Proof of Theorem 5.5 (1) First, suppose that τ : TREE m → STR in [Σ] is a basic MSOtransduction such that, for every m-coloured order-tree T ∈ dom(τ ) with image A in ∈ τ (T), we have

A ∪ E = Lf(T) and A ∩ E = ∅ .
It follows by Lemma 5.10 that there is a number w ∈ N such that, for every tree T, we can find a partition refinement of A in ∈ τ (T) with underlying tree T whose width is at most w. By Lemma 5.9 it follows that A has a tree decomposition (U v ) v∈T with underlying tree T and whose width is less than k := w(r + 3).

(2) If τ is a basic MSO-transduction such that

A ∪ E ⊆ Lf(T) and A ∩ E = ∅ , for all A in ∈ τ (T) with T ∈ dom(τ ) ,
then we can argue similarly. Let τ ′ be the MSO-transduction mapping T to the structure obtained from τ (T) by adding one isolated element for every leaf of T that does not correspond to an element of τ (T). Then τ ′ is of the form considered in (1) and we obtain a tree decomposition (U v ) v∈T of τ ′ (T). Deleting from every component U v all elements not in τ (T) we obtain the desired tree decomposition of τ (T).

(3) Suppose that τ is a non-copying MSO-transduction as in (2) but with p parameters. We can regard τ as a basic MSO-transduction TREE m+p → STR in [Σ]. By (2) it follows that, for every value of the parameters P , the structure τ (T, P ) has a tree decomposition of the required form.

(4) Finally, consider the general case. Suppose that τ is l-copying. Given T let T + be the tree obtained from T by adding l new successors to every vertex of T. Formally, suppose that T ⊆ D <ω , for some finite set D. W.l.o.g. we may assume that D ∩ [l] = ∅. We define the domain T + ⊆ (D ∪ [l]) <ω of T + by

T + := T ∪ (T × [l]) .
Furthermore, we add new colour predicates

S i := T × {i} , for i ∈ [l] .
Note that every element of τ (T) is of the form v, i where i ∈ [l] and v ∈ T . Hence, each such element corresponds to a leaf vi ∈ T × [l] ⊆ T + . Using the parameters S we can construct a basic MSO-transduction τ + : TREE m+l → STR in [Σ] satisfying the conditions of (3) such that τ + (T + ) = τ (T). By (3), we obtain a tree decomposition

H + = (U + v ) v∈T + of τ + (T + ) = τ (T). Let H = (U v
) v∈T be the tree decomposition obtained from H + by contracting every edge leading to a leaf in T + T . Then we have wd(H) + 1 ≤ (l + 1)(wd(H + ) + 1) and wd(H + ) ≤ w , for some w ∈ N independent of T .

The transduction hierarchy

The focus of our investigation lies on the following preorder on classes of structures which compares their 'encoding powers' with respect to MSO-transductions. Our main result is a complete description of the hierarchy induced by this preorder. It will be given in Theorem 6.4. Definition 6.1. Let C, K ⊆ STR. We define the following relations.

(a) C ⊑ K if there exists a transduction τ such that C ⊆ τ (K).

(b) C ⊏ K if C ⊑ K and K ⊑ C. (c) C ≡ K if C ⊑ K and K ⊑ C. (d) C ⊳ K if C ⊏ K and there is no class D with C ⊏ D ⊏ K. (e) C ⊑ in K if C in ⊑ K in .
(f) The relations ⊏ in , ≡ in , and ⊳ in are defined analogously to ⊏, ≡, ⊳ by replacing ⊑ everywhere by ⊑ in . The transduction hierarchy is the hierarchy of classes C ⊆ STR induced by the relation ⊑ in .

As the class of transductions is closed under composition, it follows that the relation ⊑ in is a preorder, i.e., it is reflexive and transitive. Lemma 6.2. ⊑ in is a preorder on P(STR). The following description of the transduction hierarchy is the main result of the present paper.

Theorem 6.4. We have the following hierarchy:

∅ ⊳ in T 0 ⊳ in T 1 ⊳ in . . . ⊳ in T n ⊳ in • • • ⊏ in P ⊳ in T ω ≡ in T bin ⊳ in G
For every signature Σ, every class C ⊆ STR[Σ] is ≡ in -equivalent to some class in this hierarchy.

Remark 6.5. There is a lot of flexibility in the choice of representatives for the various levels. For instance, we could replace T n by the class of all trees of height at most n, T ω by T bin or { 2 <n | n ∈ N }, and G by the class of square grids.

It is straightforward to show that the above classes form an increasing chain. The hard part is to prove that the chain is strictly increasing and that there are no further classes. Lemma 6.6. We have

∅ ⊑ in T 0 ⊑ in T 1 ⊑ in • • • ⊑ in T n ⊑ in • • • ⊑ in P ⊑ in T ω ⊑ in G .
Proof In the example before Lemma 3.7, we have constructed transductions τ n such that T n ⊆ τ n (P). Hence, T n ⊑ in P. The remaining assertions follow from the observation that, by Lemma 5.1, C ⊆ Min(K) implies C ⊑ in K.

Let us collect some easy properties of the hierarchy. Our first result states that G is a representative of the top level of the transduction hierarchy. Before encoding arbitrary structures in such grids we describe a transduction mapping G to its directed variant V, E 0 , E 1 where

E 0 := { ( i, k , i + 1, k ) | i < m -1, k < n } ,
and

E 1 := { ( i, k , i, k + 1 ) | i < m, k < n -1 } .
This can be done with the help of the parameters P 0 , P 1 , P 2 , Q 0 , Q 1 , Q 2 ⊆ V where

P m := { i, k | i ≡ m (mod 3) } , and
Q m := { i, k | k ≡ m (mod 3) } .
Then

E 0 = { (u, v) ∈ edg | u ∈ P i and v ∈ P j for some i ≡ j -1 (mod 3) } ,
and

E 1 = { (u, v) ∈ edg | u ∈ Q i and v ∈ Q j for some i ≡ j -1 (mod 3) } .
It is easy to write down a formula checking that the parameters P m and Q m are correctly chosen (see, e.g., [START_REF] Courcelle | The expression of graph properties and graph transformations in monadic secondorder logic[END_REF]).

To show that STR[Σ] ⊑ in G, suppose that A ∈ STR[Σ] is a structure with A in = A ∪ E, (P R ) R , in 0 , . . . , in r-1 . Fix enumerations a 0 , . . . , a m-1 of A and e 0 , . . . , e n-1 of E. By the above remarks, it is sufficient to encode A in in the directed m × n grid. Consider the following subsets of [m] × [n]:

A ′ := [m] × {0} , P ′ R := { 0, k | e k ∈ P R } , E ′ := {0} × [n] , I ′ l := { i, k | (a i , e k ) ∈ in l } .
Then A in can be recovered from G by an MSO-transduction using these sets as parameters. Lemma 6.8. T ω ≡ in T bin .

Proof For one direction, note that T bin ⊆ T ω implies T bin ⊑ in T ω . Conversely, each finite tree can be obtained as minor of a binary tree. Therefore, we have T ω ⊆ Min(T bin ) ⊑ in T bin . Lemma 6.9. We have C ≡ in T 1 if and only if C is finite and contains at least one nonempty structure. As indicated in the example before Lemma 3.7, there exists a transduction mapping an incidence structure A in to the incidence structure Gf(A) in of the Gaifman graph of A.

Strictness of the hierarchy

In this section we prove that the hierarchy is strict. Using the results of Section 5 we can characterise each level of the hierarchy in terms of tree-width and its variants.

Theorem 7.1. Let C ⊆ STR[Σ]. (a) C ⊑ in P iff pwd(C) < ∞. (b) C ⊑ in T ω iff twd(C) < ∞. (c) C ⊑ in T n iff twd n (C) < ∞.
Proof In each case (⇐) follows from Lemma 5.2 and (⇒) follows from Theorem 5.5.

Corollary 7.2. Let C be a class of Σ-structures.

(a) pwd(C) = ∞ implies T ω ⊑ in C. (b) twd(C) = ∞ implies G ⊑ in C.
Proof (a) Suppose that pwd(C) = ∞. Then Theorem 4.5 implies that T ω ⊆ Min(Gf(C)).

Hence, the claim follows from Lemmas 6.10 and 6.11. (b) Suppose that twd(C) = ∞. Then Theorem 4.6 implies that G ⊆ Min(Gf(C)). As in (a), the claim follows from Lemmas 6.10 and 6.11.

Corollary 7.3. Let C ⊆ STR[Σ]. (a) C ⊑ in P implies T ω ⊑ in C. (b) C ⊑ in T ω implies G ≡ in C.
In particular, it follows that the upper part of the hierarchy is strict:

Corollary 7.4. P ⊳ in T ω ⊳ in G
Proof Both assertions follow from Theorem 7.1 and Corollary 7.3.

For the first one, note that we have P ⊑ in T ω since P ⊆ Min(T ω ). Conversely, pwd(T ω ) = ∞ implies, by Theorem 7.1 (a), that T ω ⊑ in P. Hence, P ⊏ in T ω . Finally, if C ⊏ in T ω then C ⊑ in P, by Corollary 7.3 (a). Consequently, we have P ⊳ in T ω .

Similarly, the fact that T ω ⊑ in G follows from Lemma 6.7. Since twd(G) = ∞, Theorem 7.1 (b) implies that T ω ⊏ in G. Finally, we obtain T ω ⊳ in G by Corollary 7.3 (b).

Let us turn to the lower part. We start with two technical lemmas. Definition 7.5. Let T = T, ≤ be an order-tree. Vertices v 0 , . . . , v m-1 of T are horizontally related via a vertex w if all v i are at the same level of the tree and v i ⊓ v k = w, for all 0 ≤ i < k < m.

Lemma 7.6. Let T be a coloured order-tree of height n, and suppose that τ is a parameterless k-copying MSO-transduction of rank r such that τ (T) is a successor-tree of height at most n + 1. Consider vertices v 0 , . . . , v m-1 of T that are horizontally related via w fix some number l < k. Let x i be the successor of w with x i v i . If, for all i, j < m, we have

MTh r+2n+1 (T x i , v i ) = MTh r+2n+1 (T x j , v j ) ,
then at least m -1 elements of the set { v 0 , l , . . . , v m-1 , l } (these are elements of the domain of τ (T)) are horizontally related in τ (T).

Proof Let ϕ ss ′ (x, y) be the formula defining the successor relation in τ (T) between vertices of the form x, s and y, s ′ . By assumption the rank of ϕ ss ′ (x, y) is at most r.

First, note that a vertex v, l is on level h in τ (T) if and only if there are indices s 0 , . . . , s h-1 < k such that

T |= ψ s 0 ...s h-1 (v)
where the formula

ψ s 0 ...s h-1 (v) := ∃y 0 • • • ∃y h-1 i<h-1 ϕ s i s i+1 (y i , y i+1 ) ∧ ϕ s h-1 l (y h-1 , v) ∧ ¬∃z s<k ϕ ss 0 (z, y 0 )
expresses that there exists a path of the form y 0 , s 0 , . . . , y h-1 , s h-1 , v, l from the root y 0 , s 0 of τ (T) to the vertex v, l . By assumption on v i and Lemma 3.14, we have MTh r+2n+1 (T, v i ) = MTh r+2n+1 (T, v j ) , for all i, j .

Since the rank of ψ s 0 ...s h-1 is h + r + 1 ≤ r + 2n + 1 it follows that

T |= ψ s 0 ...s h-1 (v i ) iff T |= ψ s 0 ...s h-1 (v j ) .
Hence, all vertices v 0 , l , . . . , v m-1 , l are on the same level h in τ (T). We prove by induction on h that

( * ) MTh r+n+h+1 (T x i , i ) = MTh r+n+h+1 (T x j , v j )
implies that all but at most one of v 0 , l , . . . , v m-1 , l are horizontally related. Let u i , s i be the predecessor of v i , l in τ (T), that is,

T |= ϕ s i l (u i , v i ) .
We distinguish two cases. First suppose that u 0 ⊓ v 0 w in T. By ( * ) and Lemma 3.14, we have

MTh r+n+h+1 (T, u 0 , v 0 ) = MTh r+n+h+1 (T, u 0 , v i ) ,
for all i such that u 0 ⊓ v i w. Note that there can be at most one index i that does not satisfy this condition since, if we had u 0 ⊓ v i w and u 0 ⊓ v j w, for i = j, then we would have v i ⊓ v j ≻ w and v 0 , . . . , v m-1 would not be horizontally related via w. It follows that T |= ϕ s 0 l (u 0 , v 0 ) implies T |= ϕ s 0 l (u 0 , v i ) , for all i as above .

Hence, u 0 , s 0 is the common predecessor of all the v i , l , except for possibly one of them. (For an index i with u 0 ⊓ v i w our composition argument does not work since in that case ( * ) does not imply that the theories of (T, u 0 , v 0 ) and (T, u 0 , v i ) coincide.)

It remains to consider the case that w ≺ u 0 ⊓ v 0 . Setting

η u i := MTh r+n+h-1+1 (T x i , u i )
we have

T x 0 |= ∃z[|z| = |u 0 | ∧ η u 0 (z) ∧ ϕ s 0 l (z, v 0 )] .
Since the rank of this formula is r + n + h + 1 it follows that

T x i |= ∃z[|z| = |u 0 | ∧ η u 0 (z) ∧ ϕ s 0 l (z, v i )]
, for all i < m .

Consequently, we have |u i | = |u 0 |, for all i, and u 0 , . . . , u m-1 are horizontally related via w.

Since the vertices u 0 , s 0 , . . . , u m-1 , s 0 are on level h-1 in τ (T), we can apply the induction hypothesis and it follows that all but at most one of then are horizontally related via some vertex w ′ . Therefore, the same holds for their successors v 0 , l , . . . , v m-1 , l .

Definition 7.7. We denote by B(n, k, c) the number of functions m <n → P([c]) with m ≤ k. Intuitively, each such function corresponds to a vertex-colouring of the tree m <n with c colours.

Lemma 7.8. For n ≥ 1 and k ≥ 2, we have

2 ck n-1 ≤ B(n, k, c) ≤ k2 2ck n-1 .
Proof For m ≥ 2, we have

m n-1 ≤ m n-1 + i<n-1 m i = m n-1 + m n-1 -1 m -1 ≤ 2m n-1 . Since [m] <n = i<n m i = m n-1 + i<n-1 m i it follows that m n-1 ≤ [m] <n ≤ 2m n-1 .
Therefore, we can bound

B(n, k, c) = 2 cn + k m=2 2 c|[m] <n | from above by B(n, k, c) ≤ 2 cn + k m=2 2 c2m n-1 ≤ k2 2ck n-1
and from below by

B(n, k, c) ≥ 2 cn + k m=2 2 cm n-1 ≥ 2 ck n-1 .
Theorem 7.9. T n ⊏ in T n+1

Proof For a contradiction, suppose that there exists a transduction τ such that (T n+1 ) in ⊆ τ ((T n ) in ). Let T ord n be the class of all order-trees corresponding to successor-trees in T n , and let T col n+1 := exp 1 (T n+1 ) be the class of all coloured successor-trees with one colour whose underlying tree is in T n+1 . Since the successor-trees in T n are 1-sparse we can construct an MSO-transduction σ 0 such that (T n ) in ⊆ σ 0 (T n ). Since T ord n ≡ T n we can combine τ and σ 0 to a transduction σ such that T col n+1 ⊆ σ(T ord n ). By Lemma 7.6, it follows that there is some constant d such that every tree T ∈ σ(T ord n ) with out-degree at most k is of the form σ(T ′ ) where T ′ ∈ T ord n has out-degree at most dk. (The out-degree of an order-tree is the out-degree of the corresponding successor-tree.) Suppose that σ uses c parameters. There are B(n, dk, c) ≤ dk2 2c(dk) n-1 colourings of trees in T ord n with out-degree at most dk. On the other hand, there are

B(n + 1, k, 1) ≥ 2 k n trees in T col n+1 with out-degree at most k. For large k it follows that B(n, dk, c) ≤ dk2 2cd n-1 k n-1 < 2 k n = B(n + 1, k, 1) .
Consequently, there is some tree in T col n+1 that is not the image of a tree in T ord n . A contradiction.

Completeness of the hierarchy

We have shown that the hierarchy presented in Theorem 6.4 is strict. To conclude the proof of the theorem it therefore remains to show that there are no additional classes. We have already seen in Corollary 7.4 that T ω and G are the only classes above P. Next we shall prove that T n ⊳ T n+1 .

Lemma 8.1. Let C be a class of structures. If, for every number m ∈ N, there exists a structure A ∈ C such that we can embed m <n+1 into every tree underlying a tree decomposition

(U v ) v∈T of A of width k, then T n+1 ⊑ in C.
Proof By Lemma 4.15, it follows that, for every m ∈ N, there is a structure in C with a strict tree decomposition of width at most k and with an underlying tree T into which we can embed the tree m <n+1 . According to Proposition 5.3 there is a transduction mapping C to the class of trees underlying these strict tree decompositions. Hence, there exists a class K ⊑ in C of successor-trees containing, for every m ∈ N, some tree into which we can embed m <n+1 . Hence,

T n+1 ⊆ Min(K) ⊑ in K ⊑ in C. Theorem 8.2. Let C be a class of structures. Then T n+1 ⊑ in C implies twd n (C) < ∞.
Proof Suppose that T n+1 ⊑ in C. Then P ⊑ in C since T n+1 ⊑ in P. By Lemmas 6.10 and 6.11, this implies that P Min(Gf(C)). Therefore, we can find a path that is not in Min(Gf(C)). By Theorem 4.9, it follows that there are numbers k, l ∈ N such that twd l (C) < k.

By induction on l, we prove that twd l (C) < ∞ implies twd n (C) < ∞. For l ≤ n, there is nothing to do. For l > n, we have T n+1 ⊑ in T l , which implies that T l ⊑ in C. Consequently, it follows by Lemma 8.1 and Corollary 4.13 that twd l-1 (C) < ∞. By induction hypothesis, the result follows.

By Lemma 5.2 we obtain the following results. To conclude the proof of Theorem 6.4 it remains to show that there are no classes between the lower part of the hierarchy and its upper part. Lemma 8.5. Let C be a class of structures. If T n ⊑ in C, for all n ∈ N, then P ⊑ in C.

Proof We show the contraposition. Suppose that P ⊑ in C. We have to show that there is some n such that T n ⊑ in C. As in the proof of Theorem 8.2 it follows that there are numbers k, l ∈ N such that twd l (C) < k. Hence, we can use Lemma 5.2 to obtain a transduction τ witnessing that C ⊑ in T l . By Theorem 7.9 we have T l+1 ⊑ in T l . It follows that T l+1 ⊑ in C, as desired.

Corollary 8.6. If C ⊏ in P then there is some n ∈ N such that C ⊑ in T n .

Proof By Lemma 8.5, there is some n ∈ N such that T n+1 ⊑ in C. Hence, Corollary 8.3 implies that C ⊑ in T n .

Together, Corollaries 7.4, 8.4, and 8.6 (and the fact that every class C satisfies ∅ ⊑ in C ⊑ in G) show that every class of Σ-structures is ≡ in -equivalent to some of the classes in Theorem 6.4. This completes the proof of this theorem.

Prospects and conclusion

Above we have obtained a complete description of the transduction hierarchy for classes of finite incidence structures. The most surprising result is that the hierarchy is linear. At this point there are at least three natural directions in which to proceed.

(i) We can study the hierarchy for classes of structures, instead of classes of incidence structures. (ii) We can consider the hierarchy for classes of infinite structures. (iii) We can replace MSO by a different logic.

An answer to (ii) seems within reach, at least if we restrict our attention to countable structures. Although the resulting hierarchy is no longer linear we can adapt most of our techniques to this setting. (For an example of nonlinearity, note that the class of all countable trees and the class of all finite grids are incomparable.)

Concerning question (iii), let us remark that all results above go through if we use CMSO instead of MSO. We only need the right definition of rank for CMSO. In the proof of Theorem 7.9 we needed the fact that there are only finitely many theories of bounded rank. We can ensure this for CMSO by defining the rank as the least number n such that

• the nesting depth of quantifiers is at most n and • in every cardinality predicate |X| ≡ k (mod m) we have m ≤ n. One can check that, with this definition of rank, the proof of Theorem 3.13 also goes through for CMSO.

For logics much weaker than MSO, on the other hand, it seems unrealistic to hope for a complete description of the corresponding transduction hierarchy. For instance, a related hierarchy for first-order logic was investigated by Mycielski, Pudlák, and Stern in [START_REF] Mycielski | A lattice of chapters of mathematics (interpretations between theorems)[END_REF]. The results they obtain indicate that the structure of the resulting hierarchy is very complicated.

Finally, let us address question (i). When using transductions between structures instead of their incidence structures, we can transfer some of the above results to the corresponding hierarchy. But we presently have no complete description since we miss some of the corresponding excluded minor results. Proof There is a transduction ̺ such that C = ̺(C in ). Since S is k-sparse we can also find a transduction σ such that S in = σ(S). Consequently, Theorem 9.2. We have the following hierarchy:

C in ⊆ τ (S in ) implies C ⊆ (̺ • τ • σ)(S) ,
∅ ⊏ T 0 ⊏ T 1 ⊏ • • • ⊏ T n • • • ⊏ P ⊏ T ω ⊏ G ≡ STR[Σ]
Proof Note that all classes in Theorem 9.2 are 2-sparse. For 2-sparse classes C and K, Lemma 9.1 implies that

C ⊑ K iff C ⊑ in K .
Consequently, the result follows from Theorem 6.4. This eliminates some possibilities for intermediate classes of graphs in the hierarchy of Theorem 9.2, but to complete the picture we still need analogues of Proposition 5.3 and of Theorems 4.5 and 4.9. Furthermore, the techniques of [START_REF] Courcelle | Vertex-Minors, Monadic Second-Order Logic, and a Conjecture by Seese[END_REF] are specific to graphs (or, more generally, to relational structures where all relations are binary). Even with the results of [START_REF] Courcelle | Vertex-Minors, Monadic Second-Order Logic, and a Conjecture by Seese[END_REF] one cannot exclude the existence of a class C of arbitrary relational structures strictly between T ω and G in the CMSO-transduction hierarchy.

Open

Let us make a final comment about relational structures. An incidence structure A in can be seen as a bipartite labelled directed graph (see the remark after Definition 2.1). Furthermore, it is 1-sparse. Hence, our results use tools from graph theory, in particular those of [START_REF] Robertson | Graph Minors. I. Excluding a Forest[END_REF][START_REF] Robertson | Graph Minors. V. Excluding a Planar Graph[END_REF][START_REF] Courcelle | Vertex-Minors, Monadic Second-Order Logic, and a Conjecture by Seese[END_REF]. However, there is currently no encoding of relational structures as labelled graphs that could help to solve question (i) above.

1

  [START_REF] Courcelle | The monadic second-order logic of graphs XIV: Uniformly sparse graphs and edge set quantifications[END_REF] introduced two notions of sparsity for hypergraphs: k-sparse hypergraphs and uniformly k-sparse hypergraphs. What we call k-sparse is a slight modification of the uniform version of[START_REF] Courcelle | The monadic second-order logic of graphs XIV: Uniformly sparse graphs and edge set quantifications[END_REF].

  Definition 4.1. (a) Let G = V, edg be an undirected graph and E ⊆ edg a set of edges. We denote by E * the reflexive and transitive closure of E. Note that E * is an equivalence relation. The graph G/E is obtained by contracting all edges in E. Formally, we have G/E := W, edg 0 , where W := V /E * is the set of equivalence classes and edg 0 contains an edge between classes [x] and [y] if and only if [x] = [y] and there are representatives u ∈ [x] and v ∈ [y] with u, v ∈ edg.

  and twd(G) = twd n (G) , for all sufficiently large n ∈ N .Furthermore, pwd(G) < n(twd n (G) + 1) , for every n ∈ N .

  Definition 4.14. Let (U v ) v∈T be a tree decomposition of a structure A. (a) We define a function µ : A → T by µ(a) :

  and b ∈ L j we define a b iff i ≤ j and a, b belong to the same connected component of G ≥i , and a ∼ b iff a b and b a , or if a, b ∈ L 0 . Clearly, the relation is MSO-definable with the help of the parameters L. We claim that, for a, b / ∈ L 0 , we have a b iff µ(a) ≤ µ(b) . (⇐) Suppose that µ(a) ≤ µ(b). Then b ∈ U ⇑µ(a) . Furthermore, U ⇑µ(a) is connected since D is strict. Hence, U ⇑µ(a) is a connected component of G ≥i containing both a and b. Since |µ(a)| ≤ |µ(b)| it follows that a b. (⇒) Suppose that a b. Then there exists an undirected path π in G ≥|µ(a)| connecting a and b. Since U ⇑u ∩U ⇑v = ∅, for all u = v such that |u| = |v|, it follows that π is contained in some U ⇑v such that |v| = |µ(a)|. Since a is a vertex of π we must have v = µ(a). Furthermore, b ∈ U ⇑µ(a) since b is also a vertex of π. This implies that µ(a) ≤ µ(b).

Example 5. 8 .

 8 Let A = (A, R) be a structure with domain A = {a, b, c, d, e} and a ternary relation R = {(a, b, c) x , (a, b, d) y , (a, b, e) z } .

  y, z}. We obtain a partition refinement {a | b | c, d, e | x, y, z} {a | b} {x | c} {y | d} {z | e} {a} {b} {x} {c} {y} {d} {z} {e} where we have indicated the partition into ≈ v -classes by vertical bars. This partition refinement has width 4.

I

  u (e) := { z ∈ A | (z, e) ∈ in i for some i and u l(z) } . For e, f ∈ E ∩ W u , it follows that e ≈ u f implies I u (e) = I u (f ) .Furthermore, we obviously have |I u (e)| ≤ |e| ≤ r. It follows that C u contains at most r • |W u /≈ u | vertices.

  Definition 6.3. We consider the following subclasses of STR[{edg}]. (All trees below are considered to be successor-trees.) (a) T n := { m <n | m ∈ N } is the set of all complete m-ary trees of height n. (b) T bin is the class of all binary trees. (c) T ω is the class of all trees. (d) P is the class of all paths. (e) G is the class of all rectangular grids.

  Lemma 6.7. STR[Σ] ⊑ in G Proof Recall that the m × n grid is the undirected graph G = V, edg with vertices V = [m] × [n] and edge relation edg = ( i, k , j, l ) |i -j| + |k -l| = 1 .

Lemma 6. 10 .

 10 For every class C of structures, we have Gf(C) ⊑ in C . The next result is just a restatement of Lemma 5.1 in our current terminology. Lemma 6.11. For every class C of graphs we have Min(C) ≡ in C .

Corollary 8. 3 .

 3 If T n+1 ⊑ in C then C ⊑ in T n . Corollary 8.4. T n ⊳ in T n+1 .

  Lemma 9.1. Let C, S ⊆ STR and suppose that S is k-sparse. (a) C ⊑ in S implies C ⊑ S. (b) S ⊑ C implies S ⊑ in C.

  and S ⊆ τ (C) implies S in ⊆ (σ • τ • ̺)(C in ) .

  Problem 9.3. Is there any class C ⊆ STR[Σ] which is not ≡-equivalent to some class in the above hierarchy? Remark 9.4. If we only consider classes of graphs and if we use CMSO-transductions instead of MSO-transductions, then the following result can be used as replacement of Theorem 4.6: Theorem 9.5 ([CO07]). Let C be a class of graphs with unbounded clique-width. There exists a CMSO-transduction τ with G ⊆ τ (C).

ACHIM BLUMENSATH AND BRUNO COURCELLE*

pour la Recherce'.