Bruno Courcelle Labri
email: courcell@labri.fr

Grammars and clique-width bounds from split decompositions

published or not. The documents may come

Grammars and clique-width bounds from split decompositions

Introduction

Graph decompositions and graph complexity measures such as tree-width and clique-width are important for algorithmic purposes and graph structure theory. They are actually linearly related in many interesting cases [START_REF] Courcelle | From tree decompositions to clique-width terms[END_REF]. Tree-width, 1 clique-width and rank-width (which is equivalent to clique-width with respect to finite boundedness) are defined from hierarchical (tree-based) graph decompositions. Tree-width and clique-width occur as parameters in many fixed-parameter tractable (FPT) algorithms [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF][START_REF] Courcelle | Linear-time solvable optimization problems on graphs of bounded clique-width[END_REF][START_REF] Downey | Fundamentals of parameterized complexity[END_REF][START_REF] Fischer | Counting truth assignments of formulas of bounded tree-width or clique-width[END_REF], in particular for the verification of monadic second-order properties of graphs.

These algorithms are based on the construction of finite automata that run on algebraic terms representing tree-decompositions, or on clique-width terms in the case where the parameter is clique-width (see Definition 1.2). However, these automata cannot be implemented in the classical way because their sets of states are much to large. The notion of fly-automaton [START_REF] Courcelle | Automata for the verification of monadic second-order graph properties[END_REF][START_REF] Courcelle | Computations by fly-automata beyond monadic second-order logic[END_REF] can overcome this difficulty in many cases 1 : these automata compute their transitions instead of looking into transition tables.

Even for checking properties of graphs of bounded tree-width, it is convenient to input graphs by clique-width terms, and we develop the theory and practice of fly-automata for graphs defined in this way (cf. [START_REF] Courcelle | Automata for the verification of monadic second-order graph properties[END_REF][START_REF] Courcelle | Computations by fly-automata beyond monadic second-order logic[END_REF][START_REF] Durand | TRAG: Term Rewriting Automata and Graphs, software developped since 2015[END_REF]). As for tree-width, computing the exact clique-width of a graph is an NP-complete problem [START_REF] Fellows | Clique-width is NPcomplete[END_REF]. However, clique-width terms witnessing "good" approximations of clique-width can be used with fly-automata. Such terms can be constructed by different algorithms, and with help of modular or split decomposition 2 , in preliminary steps.

These decompositions are related to clique-width as follows. Each undirected graph has a canonical (unique up to isomorphism) modular decomposition, and also a canonical split decomposition. Its clique-width is the maximal cliquewidth of a prime module of the modular decomposition (Proposition 2.112 of [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF]). Theorems 4.15 and 5.13 prove that it is linearly bounded in terms of the maximal clique-width of a prime component of the split decomposition 3 , the other components being stars and cliques. These theorems improve the known bounds based of complicated arguments of logic.

Our motivating example is the class of distance-hereditary graphs (DH graphs in short). They are the undirected graphs G in which the distance in any connected induced subgraph is the same as the one relative to G. They are known to have clique-width at most 3 [START_REF] Golumbic | On the Clique-Width of Some Perfect Graph Classes[END_REF][START_REF] Meister | Clique-width with an inactive label[END_REF][START_REF] Oum | Rank-width and vertex-minors[END_REF]. However, recognizing the clique-width terms that define them is not easy. For the purpose of testing fly-automata, one may wish to generate large "random" DH graphs, together with the algebraic terms of clique-width 3 that denote them. A good tool consists in using a context-free graph grammar, built from clique-width operations that use three labels. The characterization of DH graphs from [START_REF] Bandelt | Distance-hereditary graphs[END_REF], based on the addition of pendant edges and twins (see Definition 1.1), uses rewriting rules that are not those of a context-free grammar appropriate for using fly-automata intended to run on their derivation trees or on the equivalent clique-width terms. However, from this characterization, we can construct such a context-free grammar based on vertex-replacement, a notion developped in [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF] (also [START_REF] Courcelle | An axiomatic definition of context-free rewriting and its application to NLC graph grammars[END_REF] for an axiomatic approach to context-free graph grammars).

This construction uses a generalization of the standard notion of substitution of a graph for a vertex, that underlies the theory of modular decomposition. We distinguish in a graph H some vertices as dead : they will not be linked to any others in case H is substituted into another graph 4 . We use this notion of substitution to define an associated notion of context-free vertex-replacement grammar (see [START_REF] Courcelle | An axiomatic definition of context-free rewriting and its application to NLC graph grammars[END_REF][START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF] for these graph grammars). We obtain a very simple grammar for DH graphs. Distance-hereditary graphs are also easily characterized in terms of their canonical split decompositions, and our grammar somehow translates these decompositions.

Generalizing this observation, we use our grammars to generate the graphs whose prime components (relative to split decomposition) belong (up to isomorphism) to a fixed finite set M. We bound their clique-width in terms of the maximal clique-width of a graph in M, in a better way than what is known from [START_REF] Courcelle | The monadic second-order logic of graphs XVI : Canonical graph decompositions[END_REF].

Split decomposition 5 for strongly connected (directed) graphs has also been studied in [START_REF] Courcelle | The monadic second-order logic of graphs XVI : Canonical graph decompositions[END_REF][START_REF] Cunningham | Decomposition of directed graphs[END_REF]. We extend to directed graphs our results for undirected graphs. For expressing split decompositions in terms of graph substitution, we need a more involved notion of substitution. Whereas for undirected graphs, we distinguish dead vertices from live ones (the others), for directed graphs, we need three types of live vertices, in order to encode three types of connections between two vertices u and v : from u to v (only), from v to u (only) or in both directions.

We consider split decompositions of directed graphs that need not be strongly connected, and we handle them formally as graph-labelled trees, a notion used in [START_REF] Courcelle | The monadic second-order logic of graphs XVI : Canonical graph decompositions[END_REF][START_REF] Gioan | Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF]. We prove that the clique-width of a directed graph G is bounded by 8k +1, where k is the maximum clique-width of a component of a graph-labelled tree that defines G, or of its canonical split decomposition when it is strongly connected.

To summarize, the purpose of this article is to clarify the close relationships between split decomposition, clique-width and vertex-replacement graph grammars based on vertex substitutions. In particular, we translate split decompositions of undirected graphs into graph grammars (based on appropriate substitutions to vertices) and we bound linearly the clique-width of a decomposed, directed or undirected graph, in terms of those of the components. Section 1 is devoted to basic definitions. Section 2 introduces vertex substitutions for undirected graphs with dead vertices, and the corresponding grammars. Section 3 relates clique-width and substitutions. Section 4 studies split decomposition of undirected graphs in this perspective, with the help of graph-labelled trees. Section 5 develops the case of directed graphs.

Acknowledgement: I thank I. Durand, E. Gioan, M. Kanté, S. Oum and C. Paul for their useful comments. I also thank the editors of the special issue of Discrete Applied Mathematics relative to the GROW meeting in Toronto, in 2017 for wellcoming this submission.

Graphs and clique-width

Most definitions are well-known, we mainly review notation. We state a few facts that are either well-known or easy to prove.

The union of two sets is denoted by ⊎ in cases where we stress they are disjoint. The cardinality of a set X is denoted by |X| and its powerset by P(X). The set of integers {1, ..., n} is denoted by [n].

All trees and graphs are nonempty and finite.

Trees

The set of nodes of a tree T is denoted by N T , its set of leaves, i.e., of nodes of degree 1, by L T .

If T has a root, denoted by root T , then < T denotes the corresponding ancestor relation, a strict partial order on N T (a node is not an ancestor of itself). The root is the unique maximal element and the leaves different from the root are the minimal ones. A star S n is a tree with n -1 ≥ 2 leaves linked to a single node called its center.

Graphs

We consider simple graphs, i.e., that are loop-free and without parallel edges. Graphs are directed or not. Directed graphs may have pairs of opposite edges. Undefined notions are as in [START_REF] Diestel | Graph theory[END_REF]. A graph G has vertex set V G and edge set E G . The corresponding binary adjacency relation is denoted by edg G . If G is undirected, we denote by uv or vu an edge between u and v. If G is directed, we denote by uv an edge from u to v.

We denote by G

[X] the induced subgraph of G with vertex set X ⊆ V G , by G -X the graph G[V G -X] and by G -x the graph G[V G -{x}] where x ∈ V G .

Definition 1.1 : Distance hereditary graph

An undirected graph G is distance hereditary (DH in short) if the distance of two vertices in every connected induced subgraph is the same as in G. For an example, the cycle C 4 (with 4 vertices) is DH whereas C 5 is not. The DH graphs are characterized as follows 6 : a DH graph is an isolated vertex, or the disjoint union of two DH graphs or is obtained from a DH graph by the addition of a pendant edge to a vertex x, or of a twin to x. Adding to x a true twin is adding a new vertex y linked to x and to the neighbours of x. Adding a false twin is similar with y not linked to x.

Labelled graphs.

Let C be a finite set of labels

. A C-graph is a triple G = (V G , E G , π G ) where π G is a mapping: V G → C. Its type, denoted by τ (G) is π G (V G ), i.e.
, the finite set of labels from C that label some vertex of G.

We denote by ≃ the isomorphism of C-graphs up to vertex labels, i.e., the isomorphism of the underlying unlabelled graphs, and by ≡ the existence of an isomorphism that respects labels. An abstract C-graph is an equivalence class of graphs for ≡.

Clique-width

Clique-width is based on operations that modify or combine C-graphs. There will be some restrictions regarding the special label ⊥ (see Section 3 below). -the unary operation8 relab h that changes every vertex label a into h(a) where h is a mapping from C to C, -and, for each a ∈ C, the nullary symbol a(x) that denotes the isolated vertex x labelled by a.

We denote by F C as the set of these operations 9 . A term over F C is wellformed if no two occurrences of nullary symbols designate the same vertex ; in particular, the graphs defined by the two arguments of an operation ⊕ are disjoint. We denote by T (F C ) the set of well-formed terms. We call them cliquewidth terms. Each such term t denotes a C-graph val(t) whose vertices are exactly those specified by the nullary symbols of t. Its width is the number of labels that occur in t.

The clique-width of a labelled graph 10 G, denoted by cwd(G), is the least width of a term t such that G ≃ val(t). We denote by cwd * (G) the least width of t such that G ≡ val(t). Hence, cwd(G) ≤ cwd * (G). Clearly, cwd(G) = cwd * (G ′ ) where G ′ is obtained from G by relabelling all its vertices in the same way.

Here are some examples. The clique-width of a tree is at most 3, that of the clique K n is 2 for n ≥ 2. The undirected cycles C 3 , C 4 have clique-width 2, C 5 , C 6 have clique-width 3, and C n has clique-width 4 for n ≥ 7. For directed cycles -→ C n , we have cwd(

-→ C 3 ) = 3 and cwd( -→ C n ) = 4 if n ≥ 4.
Lemma 1.3 : For every labelled graph G, we have :

max{|τ (G)| , cwd(G)} ≤ cwd * (G) ≤ |τ (G)| • cwd(G).
Proof: The first inequality is clear from definitions. To prove the second one, we assume without loss of generality, that the type of G is [p]. Let H be G with all vertices labelled in the same way. Let C be the set of k labels of a term t that defines H. For each a in C and i ∈ [p], we define a new label (a, i) that will only label the vertices x such that π G (x) = i.

Consider in t a nullary symbol a(x). If π G (x) = i, we replace it by (a, i)(x).

Each relabelling relab h is replaced by relab h ′ where h ′ maps (a, i) to (b, i) whenever h maps a to b. Similarly, we replace add a,b by the composition of the operations add (a,i),(b,j) for i, j ∈ [p]. We obtain in this way a term 11 t ′ . We let

h ′′ : C ×[p] map each label (a, i) to i for each a ∈ C. Then G = relab h ′′ (val(t ′ )) = val(relab h ′′ (t ′ )).
The term relab h ′′ (t ′ ) uses at most p + p.k labels. However, we can fix some a ∈ C and replace everywhere (a, i) by i, for each i. We obtain a term of width at most p.k that defines G.

Hence if the type of G consists of p labels and k is the clique-width of the corresponding unlabelled graph, then one can define G, with its labelling, by a term with at most p.k labels. This lemma implies that cwd(G) ≤ 2cwd(Gx) if x is a vertex of G. This bound is proved in [START_REF] Gurski | The behavior of clique-width under graph operations and graph transformations[END_REF]. Can it be improved 12 ? Can one improve the bound p.k in Lemma 1.3 13 ?

We will also use nullary symbols a that do not designate any particular vertex. In this case, the vertex defined by an occurrence u of a in a term is u itself. We will also consider that a term written with such nullary symbols denotes an abstract graph. See [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], Section 2.52. We will denote by F C the signature F C where the symbols a(x) are replaced by a, and by t the term in T (F C ) obtained from a term t ∈ T (F C ) by replacing each by a(x) by a. Then val(t) ≡ val(t).

Substitution to vertices

We consider undirected graphs in this section. We will adapt the definitions for directed graphs in Section 5.

Let C be a set of labels containing ⊥ . The vertices of a graph G labelled by ⊥ will be said to be dead ; they form the set V dead G . The others, said to be live, form the set V live G . The unary operation κ, read kill, relabels all vertices by ⊥ hence makes them dead. Definition 2.1 : Substitution. Let K be a C-graph and x 1 , . . . , x p be pairwise distinct vertices. Let H 1 , . . . , H p be pairwise disjoint C-graphs, that are disjoint 14 from K. We define a C-graph as follows:

G := K[H 1 /x 1 , . . . , H p /x p ] where V G := (V K -{x 1 , . . . , x p }) ⊎ V H1 ⊎ . . . ⊎ V Hp , π G (v) := π K (v) if v ∈ V K -{x 1 , . . . , x p }, π G (v) := π K (x i ) if v ∈ V live Hi , π G (v) := ⊥ if v ∈ V dead Hi .
Its edges are as follows, for u, v in V G :

uv ∈ E G if and only if : either uv ∈ E K and neither u nor v is in {x 1 , . . . , x p }, or uv ∈ E H i for some i,

or u ∈ V K , ux i ∈ E K and v ∈ V live

Hi

(or vice-versa since we define undirected graphs),

or u ∈ V live H i , v ∈ V live H j and x i x j ∈ E K (so that i = j).
The type of G is thus that of K, possibly augmented with ⊥ if some H i has dead vertices (these vertices are dead in G). The labels of K have no influence on the definition of the edges of G. They are only used for defining the labels of the resulting graph G. The labels of the graphs H i other than ⊥ do not appear in G: hence, if we have h i (a) = ⊥ if and only if a = ⊥, for each i, then :

K[H 1 /x 1 , . . . , H p /x p ] = K[relab h 1 (H 1 )/x 1 , . . . , relab h p (H p )/x p ].
If all vertices of H p are dead, then

K[H 1 /x 1 , . . . , H p /x p ] = (K -x p )[H 1 /x 1 , . . . , H p-1 /x p-1 ] ⊕H p .
Because of dead vertices, this notion of substitution differs from the classical one, use in particular in the theory of modular decomposition (see the survey [START_REF] Habib | A survey of the algorithmic aspects of modular decomposition[END_REF]). Proposition 2.2 : Let K, H 1 , H 2 be pairwise disjoint C-graphs and

x 1 ∈ V K . (1) If x 2 is another vertex of K, then K[H 1 /x 1 ][H 2 /x 2 ] = K[H 1 /x 1 , H 2 /x 2 ]. (2) If x 2 ∈ V H 1 , then K[H 1 /x 1 ][H 2 /x 2 ] = K[H 1 [H 2 /x 2 ]/x 1 ].
Proof : (1) Straightforward verification from the definitions.

(

) Let G := K[H 1 /x 1 ][H 2 /x 2 ] and G ′ := K[H 1 [H 2 /x 2 ]/x 1 ]. Clearly, V G = V G ′ . Let u, v belong to V G . If u and v are both, either in V K , or in V H1 or in V H2 , then uv ∈ E G if and only if uv ∈ E G ′ . Otherwise we distinguish three cases. (i) u ∈ V K and v ∈ V H 1 ; then, uv ∈ E G if and only if ux 1 ∈ E K and v is live in H 1 , if and only if uv ∈ E G ′ . (ii) u ∈ V K and v ∈ V H2 ; then, uv ∈ E G if and only if ux 2 ∈ E K[H1/x1] and v is live in H 2 . The condition ux 2 ∈ E K[H1/x1] is equivalent to : ux 1 ∈ E K and x 2 is live in H 1 . Now uv ∈ E G ′ if and only if ux 1 ∈ E K and v is live in H 1 [H 2 /x 2 ] which is true if and only if v is live in H 2 and x 2 is live in H 1 . Hence, uv ∈ E G if and only if uv ∈ E G ′ . (iii) u ∈ V H 1 -{x 2 } and v ∈ V H 2 ; then uv ∈ E G if and only if ux 2 ∈ E H 1 and v is live in H 2 , if and only if uv ∈ E H1[H2/x2] , if and only if uv ∈ E G ′ . It remains to verify that π G = π G ′ . If u ∈ (V K -{x 1 }) ⊎ (V H 1 -{x 2 }), then π G (u) = π G ′ (u) because u is not affected by the substitutions to x 2 . If u ∈ V H2 , then π G (u) = ⊥ if u is dead in H 2 ; it is π K[H1/x1] (x 2 ) otherwise; but π K[H1/x1] (x 2 ) = ⊥ if x 2 is dead in H 1 , otherwise π K[H1/x1] (x 2 ) = π K (x 1 ). Now, π G ′ (u) = ⊥ if u is dead in H 1 [H 2 /x 2 ] and it is π K (x 1 ) otherwise; observe that u is dead in H 1 [H 2 /x 2 ] if and only if it is dead in H 2 or x 2 is dead in H 1 . We obtain π G (u) = π G ′ (u) in this case; this value is either π K (x 1 ) or ⊥ (if u is dead in H 2 or x 2 is dead in H 1 ). 2
This completes the proof.

In [START_REF] Courcelle | An axiomatic definition of context-free rewriting and its application to NLC graph grammars[END_REF], Properties (1) and ( 2) are called respectively commutativity and associativity of substitution. They are axioms for the definition of context-free graph grammars based on an abstract notion of substitution. These grammars are particular vertex replacement grammars [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF]. Definition 2.3 : Graph operations based on substitution. (a) For each C-graph K with vertex set enumerated as {x 1 , . . . , x p }, we define as follows a p-ary graph operation 15 on C-graphs denoted by σ

[K, x 1 , . . . , x p ] : σ[K, x 1 , . . . , x p ](H 1 , . . . , H p ) := K[H 1 /x 1 , . . . , H p /x p ]
where H 1 , . . . , H p are pairwise disjoint C-graphs that are disjoint from K. Note that the vertex set of σ

[K, v 1 , . . . , v p ](H 1 , . . . , H p ) is V H1 ⊎ . . . ⊎ V Hp .
If H 1 , . . . , H p are not pairwise disjoint, we replace them by isomorphic copies in a standard way ([14], Chapter 2), so that σ[K, x 1 , . . . , x p ] becomes a p-ary operation on abstract C-graphs, (i.e., isomorphism classes of C-graphs).

We denote by Σ C the countable set of these operations together with the nullary symbols a(x) to denote vertices.

A term in T (Σ C ) is well-formed if each vertex x occurs at most once in a symbol a(x). Every well-formed term t denotes a graph val(t). The signature Σ C is obtained from Σ C by replacing, for each a, the different symbols a(x) by a. As for clique-width terms in T (F C ), each term in T (Σ) denotes an abstract graph.

We denote by relab a the relabelling that replaces by a every label except ⊥.

Proposition 2.4 : Let t, t ′ ∈ T (Σ C ) and x be a vertex in val(t) defined by a nullary symbol a(x). Let t ′ be a term such that V val(t ′ ) ∩ (V val(t) -{x}) = ∅. Then, we have :

val(t)[val(t ′ )/x] = val(t[relab a (t ′ )/a(x)]). The term t[relab a (t ′ )/a(x)] is obtained by substituting t ′ in t for the unique occurrence of a(x). It is well-defined because V val(t ′ ) ∩ (V val(t) -{x}) = ∅ (cf.
the footnote in Definition 2.1).

Proof : By induction of the structure of t.

If t = a(x), then val(t[relab a (t ′ )/a(x)] = val(relab a (t ′ )) = a(x)[val(t ′ )/x])
by the definition of substitution, hence is equal to val(t)[val(t ′ )/x].

Let t = σ[K, v 1 , . . . , v p ](t 1 , . . . , t p ). Without loss of generality and to simplify notation, we assume that a(x) occurs in t 1 . Then,

t[t ′ /a(x)] = σ[K, v 1 , . . . , v p ](t 1 [t ′ /a(x)], t 2 , . . . , t p ); val(t[t ′ /a(x)]) = K[val(t 1 [t ′ /a(x)])/v 1 , val(t 2 )/v 2 , . . . , val(t p )/v p ].
By induction :

val(t 1 [t ′ /a(x)]) = val(t 1 )[val(t ′ )/x], hence val(t[t ′ /a(x)]) = K[val(t 1 )[val(t ′ )/x]/v 1 , . . . , val(t p )/v p ] = K[val(t 1 )/v 1 , . . . , val(t p )/v p ][val(t ′ )/x] by Propoposition 2.2(2), = val(t)[val(t ′ )/x].
From these operations one can define grammars, formalized by systems of recursive equations in sets of abstract C-graphs of which one takes least solutions (cf. [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], Chapter 3 for "context-free" grammars in a universal algebra setting). We first consider some examples. Definitions 2.5 : Some basic operations.

Here are operations of particular interest. They concern D-graphs where D := {⊥, ⊤} (and ⊤ labels live vertices).

H 1 ⊕H 2 = σ[K, x 1 , x 2 ](H 1 , H 2 )
where K consists of two isolated live vertices x 1 and x 2 .

H 1 ⊗ H 2 := σ[K, x 1 , x 2 ](H 1 , H 2 )
where K is the edge x 1 x 2 and x 1 and x 2 are live.

We will also use :

Λ(H 1 , H 2 ) := σ[K, x 1 , x 2 ](H 1 , H 2 ) where K is the edge x 1 x 2 , x 1 is live and x 2 is dead.
We have :

κ(H) = σ[K, x 1 ](H) where K consists of the dead vertex x 1 .
The operations ⊕ and ⊗ are associative and commutative. Here are some algebraic properties of the other ones:

Λ(Λ(G, H 1 ), H 2 ) = Λ(Λ(G, H 2 ), H 1 ) = Λ(G, H 1 ⊕ H 2 ), κ(Λ(G, H)) = κ(G ⊗ H), Λ(κ(G), H) = κ(G) ⊕ κ(H).
We let Σ dh be the signature {⊕, ⊗, Λ, κ, ⊤} ⊆ Σ D . We need not use the nullary symbols ⊥(x) because a dead vertex x can be defined by κ(⊤(x)). Actually, a vertex introduced as dead remains isolated.

Examples 2.6 : Some grammars (equations in sets of D-graphs) over Σ dh .

(1) The equation

X = ⊤ ∪ (X ⊕ X) ∪ (X ⊗ X)
defines the set of cographs (all vertices are live, as ⊕ and ⊗ do not introduce dead vertices). Here X denotes a set of abstract {⊤}-graphs, X ⊕ X denotes {G ⊕ H | G, H ∈ X}, and similarly for the other operations.

This equation can also be solved in the set of terms T ({⊕, ⊗, ⊤}). Then X denotes a subset of T ({⊕, ⊗, ⊤}) and X ⊕ X denotes the set of terms {t ⊕ t ′ | t, t ′ ∈ X} (and similarly for ⊗). We obtain the set of terms L(X).

More generally, for a system of recursive equations with unknowns X, Y, Z, ... we denote by L(X), L(Y ), L(Z),... the sets of terms. A fundamental property of these systems ( [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], Proposition 3.23) establishes that the corresponding sets of objects X, Y, Z (elements of the relevant algebra) are the sets of values of the terms in L(X), L(Y ), L(Z),... Here, we get that the cographs are the values of the terms in L(X), where terms are evaluated as abstract graphs. In the present case, we have L(X) = T ({⊕, ⊗, ⊤}), hence the cographs are defined by all terms in T ({⊤, ⊕, ⊗}).

(2) The rooted trees are defined by the equation

R = ⊤ ∪ Λ(R, R).
In a tree defined in this way, only the root is live. Another grammar for trees, using two equations, is :

Y = ⊤ ∪ Λ(⊤, Z), Z = Y ∪ (Z ⊕ Z).
Here, Z defines forests, i.e., nonempty disjoint unions of rooted trees. Trees (without distinguished root) are defined by the additional equations

T = κ(R) or T = κ(Y ).
For example, the tree with nodes u, v, w, x, y, z, root x and edges xy, xz, xv, zu and vw is defined by the term :

Λ(Λ(Λ(⊤(x), ⊤(y)), Λ(⊤(z), ⊤(u))), Λ(⊤(v), ⊤(w)))
belonging to L(Y ) or by the term of L(U) :

Λ(⊤(x), ⊤(y) ⊕ Λ(⊤(z), ⊤(u)) ⊕ Λ(⊤(v), ⊤(w))).
The paths with one live vertex at one end are defined by the equation

P = ⊤ ∪ Λ(⊤, P ).
(3) We will prove below that the equation

W = ⊤ ∪ (W ⊕ W ) ∪ (W ⊗ W ) ∪ Λ(W, W )
defines, up to vertex labels, the distance hereditary graphs.

From these equations, we obtain that the rooted trees are defined by all terms in T ({Λ, ⊤}) or by certain terms in T ({⊕, Λ, ⊤}), and that the distance hereditary graphs are defined by terms in T ({⊕, ⊗, Λ, ⊤}). In these equations and the generated terms, the label ⊥ for dead vertices does not appear explicily, but it is introduced by the operations Λ and κ.

In the following description of DH graphs, all vertices are defined as dead, equivalently, unlabelled (there is no reason to distinguish any vertices as "roots").

The following recursive definition of DH graphs has been established in [START_REF] Chang | Dynamic programming on distance-hereditary graphs[END_REF], but we think interesting to prove it by using the concepts of this article. We recall that equation systems always define abstract graphs. Proposition 2.7 : (1) The DH graphs form the set X defined by the two equations :

X = κ(W ), W = ⊤ ∪ (W ⊕ W ) ∪ (W ⊗ W ) ∪ Λ(W, W ).
(2) The connected DH graphs form the set Y defined by the equation :

Y = κ(⊤) ∪ κ(W ⊗ W )
and the equation of ( 1) that defines W .

Proof : (1) Note that 16 L(W ) = T ({⊕, ⊗, Λ, ⊤}). For both direction we will use the characterization of DH graphs recalled in Definition 1.1.

(a) Every DH graph G is in the set val(X) = val(κ(W )).

We use induction on the number n of vertices of G.

If n = 1, then G is a single dead vertex, hence is G ≡ κ(⊤) ∈ κ(W ).
Otherwise there are four cases.

(i) G is the disjoint union of two DH graphs H, H ′ . Then, H ≡ κ(t), H ′ ≡ κ(t ′ ) for some t, t ′ ∈ W = T ({⊕, ⊗, Λ, ⊤}). Hence, G ≡ κ(t⊕t ′ ) where t⊕t ′ ∈ W because κ(t ⊕ t ′ ) ≡ κ(t) ⊕ κ(t ′ ). (ii) If G is obtained from a DH G ′ by adding a pendant vertex y to a vertex x of G ′ , we have G = G ′ [H/x]
where H is the edge xy, with x live and y dead 17 ; hence H = val(Λ(⊤(x), ⊤(y))).

We have G ′ = κ(val(t ′ )) where t ′ is a well-formed term over ⊕, ⊗, Λ and the nullaries that define vertices. It has one occurrence of ⊤(x).

We let t := t ′ [Λ(⊤(x), ⊤(y))/⊤(x)]. By Proposition 2.4, we have val(t) = val(t ′ )[H/⊤(x)]. Hence G = κ(t), so that G ≡ κ(t) where t ∈ W is obtained from t by replacing by ⊤ the symbols ⊤(z) that define vertices.

(iii) If G is obtained from a DH G ′ by adding a false twin y to a vertex x. We have G = G ′ [H/x] where H consists of two isolated live vertices x and y. Hence H = val(⊤(x) ⊕ ⊤(y)). The proof continues as in (ii) with ⊤(x) ⊕ ⊤(y) instead of Λ(⊤(x), ⊤(y)).

(iv) If G is obtained from DH G ′ by adding a true twin y to a vertex x. Here G = G ′ [H/x] where H consists of two live vertices x and y linked by an edge, hence H = val(⊤(x) ⊗ ⊤(y)). The proof continues as in (iii) with ⊤(x) ⊗ ⊤(y) instead of ⊤(x) ⊕ ⊤(y).

(b) Conversely, let G = val(t) for some well-formed term t over ⊕, ⊗, Λ and the nullaries that define vertices. We prove that κ(G) is DH by induction on the size of t.

If t = ⊤(x), the result holds because an isolated vertex is DH. Otherwise, we can find a position u in t such that t/u, the subterm of t issued from position u is either Λ(⊤(x), ⊤(y)) or ⊤(x)⊕⊤(y), or ⊤(x)⊗⊤(y). Then t = t ′ [(t/u) /⊤(x)] for some well-formed term t ′ (obtained by replacing in t the subterm t/u by ⊤(x)). By induction, κ(val(t ′ )) is a DH graph G ′ and G = G ′ [H/x] by Proposition 2.6, where H is respectively as in cases (ii), (iii) or (iv).

(2) It is clear that a term t in L(X) defines a connected graph if and only if it is not of the form κ(t 1 ⊕ t 2 ). Hence, the connected DH graphs can be defined by the equation :

Y = κ(⊤) ∪ κ(W ⊗ W ) ∪ κ(Λ(W, W ))
where W is as in [START_REF] Bandelt | Distance-hereditary graphs[END_REF]. However, we observed that κ(Λ(G, H)) = κ(G ⊗ H) for all D-graphs G and H. Hence, the term κ(Λ(W, W )) can be removed.

The bipartite DH graphs are built from isolated vertices by the addition of pendant edges and of false twins [START_REF] Bandelt | Distance-hereditary graphs[END_REF]. Hence, they form the set B defined by the two equations B = κ(W ′ ) and

W ′ = ⊤ ∪ (W ′ ⊕ W ′ ) ∪ Λ(W ′ , W ′ ).
3 Clique-width and substitution operations.

Substitutions as derived clique-width operations.

We recall 18 that a derived operation relative to an algebra M over a functional signature F is defined by a term t in T (F, {u 1 , ..., u p }), i.e., a term over F with variables (nullary symbols to which values or terms can be substituted) u 1 , ..., u p . The corresponding p-ary function t M is defined by evaluating t with p arguments from the domain of M as values of u 1 , ..., u p .

For an example using clique-width operations, the operation ⊗ on graphs of type {⊤} (cf. Definition 2.3) adds to the disjoint union of the two argument graphs G and H all possible edges between the vertices of G and those of H. We have G ⊗ H = relab a→⊤ (add ⊤,a (G ⊕ relab ⊤→a (H)). Hence, ⊗ is defined by the term 19 relab a→⊤ (add ⊥,a (u 1 ⊕ relab ⊤→a (u 2 )).

We let Lin(F C , {u 1 , ..., u p }) be the set of terms where each variable u i has a unique occurrence and no other nullary symbol occurs. Every such term defines a p-ary mapping on C-graphs denoted by t G . For pairwise disjoint graphs H 1 , . . . , H p , the vertex set of t G (H 1 , . . . , H p ) is V H1 ⊎ . . . ⊎ V Hp . Our objective is to express the operations σ[K, x 1 , . . . , x p ] as derived operations over F C , the signature upon which clique-width is based.

We define T ⊥ (F C ) as the set of terms that use neither the operations 20 add a,⊥ , add ⊥,b (nor the similar ones that define directed edges), nor relab h such that h(⊥) = ⊥, nor the nullary symbols ⊥(x). We denote by cwd ⊥ (G) the minimal cardinality of C -{⊥} such that G ≃ val(t) for some term t ∈ T ⊥ (F C ). Clearly, cwd(G) ≤ cwd ⊥ (G) + 1. We have cwd(T ) = 3 and cwd ⊥ (T ) = 2 for any tree T that is not a star.

Let K be a C-graph with vertex set {x 1 , . . . , x p } defined by a term t in T ⊥ (F C ). Each vertex x i is defined by a nullary symbol a i (x i ) in t (a i = ⊥ ). We define t := t[u 1 /a 1 (x 1 ), . . . , u p /a p (x p )]. This term is in Lin(F C , {u 1 , ..., u p }). We recall that relab a is the relabelling that replaces by a every label except ⊥. Lemma 3.1 : For pairwise disjoint C-graphs H 1 , . . . , H p , we have:

σ[K, x 1 , . . . , x p ](H 1 , . . . , H p ) = t G (relab a 1 (H 1 ), . . . , relab a p (H p )).
Proof: By induction on the structure of t. If t = a 1 (x 1 ), then t = u 1 and σ[K, x 1 ](H 1 ) = relab a 1 (H 1 ) by the definition of substitution, hence is t G (relab a1 (H 1 )).

If t = t 1 ⊕ t 2 , then, without loss of generality, we assume that the vertices of K 1 := val(t 1 ) are x 1 , . . . , x i and those of K 2 := val(t 2 ) are x i+1 , . . . , x p . We have t = t 1 ⊕ t 2 . Then, since substitution distributes over disjoint union 21 and by induction :

σ[K, x 1 , . . . , x p ](H 1 , . . . , H p ) = σ[K 1 , x 1 , . . . , x i ](H 1 , . . . , H i ) ⊕ σ[K 2 , x i+1 , . . . , x p ](H i+1 , . . . , H p ) = t 1G (relab a 1 (H 1 ), . . . , relab a i (H i ))⊕ t 2G (relab a i (H i ), . . . , relab a p (H p )) =
t G (relab a1 (H 1 ), . . . , relab ap (H p )).

If t = f(t 1 ) where f is relab h or add a,b , then the result holds because, for every C-graph K with vertices x 1 , . . . , x p , we have :

σ[f(K), x 1 , . . . , x p ](H 1 , . . . , H p ) = f(σ[K, x 1 , . . . , x p ](H 1 , . . . , H p )).
The equality to be proved follows then by induction.

We will denote by t K and t K terms associated with K as above. We say that an operation σ[K, x 1 , . . . , x p ] has width k if cwd ⊥ (K) = k. The operations ⊕, ⊗, Λ and κ have respective widths 2,2,2 and 1.

Proposition 3.2 : If G ≡ val(s) for some term s in T (Σ C ) whose operations have width at most k, then cwd ⊥ (G) ≤ k and cwd(G) ≤ k + 1.
Proof : By induction on the structure of s, we define a term s in T (F C ) such that val( s) ≡ val(s).

If s = a(x 1 ), then s := s.

If s = σ[K, x 1 , . . . , x p ](s 1 , . . . , s p ) then, we let t K ∈ Lin(F C , {u 1 , ..., u p }) be a term associated with K as in Lemma 3.1, and we define

s := t K [relab a 1 ( s 1 )/u 1 , . . . , relab a p ( s p )/u p ].
It is clear that val( s) ≡ val(s). The set of labels used in s is the set of all those used in the terms t K . We now bound cwd ⊥ (G). Without loss of generality, we can assume that all labels of the terms that define the operations that occur in s are in a set C such that C -{⊥} has cardinality k. Hence cwd ⊥ (G) ≤ k and cwd(G) ≤ k + 1.

If in s, all the operations of maximal width k do not use ⊥ in their definitions by terms, then cwd(G) = cwd ⊥ (G) ≤ k.

We obtain that distance hereditary graphs have clique-width at most 3 (known from [START_REF] Golumbic | On the Clique-Width of Some Perfect Graph Classes[END_REF][START_REF] Oum | Rank-width and vertex-minors[END_REF]) because they are defined with the operations κ, Λ, ⊕ and ⊗ of width at most 2. As the operation Λ of width 2 needs ⊥ in its defining term, we do not have cwd(G) = cwd ⊥ (G) ≤ 2. Proposition 4.9 of [START_REF] Meister | Clique-width with an inactive label[END_REF] establishes that conversely, G is distance hereditary if cwd ⊥ (G) ≤ 2.

Split decomposition

The split decomposition of directed and undirected graphs has been defined and studied by Cunnigham in [START_REF] Cunningham | Decomposition of directed graphs[END_REF]. We will formulate it in terms of graph-labelled trees as in [START_REF] Gioan | Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF] (called and split-decomposition graphs in [START_REF] Courcelle | The monadic second-order logic of graphs XVI : Canonical graph decompositions[END_REF]). We only consider undirected graphs in this section. Definition 4.1 : Graph-labelled trees and the graphs they describe. We denote by L T the set of leaves of a tree T and by Inc T (v) the set of edges incident to a node v.

(a) A graph-labelled tree, denoted by T is a tree T with at least three nodes that is equipped, for each node v ∈ N T , with a connected graph H v , called a component, and a bijection ρ v : Inc T (v) → V Hv . The components are pairwise disjoint. We identify u and the unique vertex of H u if u is a leaf.

(b) The corresponding split-graph S(T ) is the union of the components together with the edges ρ u (e)ρ v (e) for e = uv, (cf. Figure 1). A path in S(T ) is alternating if no two consecutive edges are in a same component. Between any two vertices x, y of S(T ), there is at most one alternating path. If there is one, we say that x is accessible from y. We add through z (or e) to indicate that this path goes through a particular vertex z (or edge e). For a vertex w of S(T ) belonging to a component H u , we denote by A(w) (respectively by P (w)) the set of vertices accessible from w by a nonempty alternating path whose first edge is not in H u (reachable from w by a nonempty path in S(T ) whose first edge is not in H u ).

(c) The graph described by T , denoted by G(T ), has vertex set L T and an edge uv if and only if u is accessible from v. It is connected ( [START_REF] Gioan | Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF], Lemma 2.3) Figure 1: A graph-labelled tree T . because the components are defined as connected 22 .

(d) Let e = uv be an edge of T between two internal nodes. The nodejoining operation (cf. [START_REF] Gioan | Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF]) contracts this edge, hence fuses u and v into a single node say w, giving tree T ′ ; it replaces H u ⊎ H v by the connected graph H ′ w := H u ⊎ H v -{ρ u (e), ρ v (e)} and with an edge between any vertex x in H u and any vertex y in H v such that xρ u (e) ∈ E H u and ρ v (e)y ∈ E H v . We obtain a graph-labelled tree T ′ that describes the same graph. If ρ u (e) has degree r in H u and ρ v (e) has degree s in H s the resulting component H ′ w has a subgraph isomorphic to the complete bipartite graph K r,s . The opposite transformation is called node-splitting. It preserves also the defined graph.

Example 4.2 : Figure 1 shows a graph-labelled tree with leaves 1, ..., 8 and internal nodes u, v, w, x. The associated graph G is in Figure 2. There is an alternating path between leaf 7 and leaf 1. Hence, they are adjacent vertices in G. On any path between 3 and 7, there are at least two consecutive edges of H u , hence, 7 is not adjacent to 3. Remark 4.3 : A graph consisting of a single edge is defined by a graph labelled tree one component of which is an edge. Otherwise, all single edge components can be eliminated by node-joinings. The resulting tree has no node of degree 2.

However in a graph-labelled tree T that defines a graph with at least 2 vertices, it may be useful to insert a component consisting of a single edge (cf. Example 4.12 below): consider an edge uv of T , replace it by two edges uw and wv where w is new node, and define the new component corresponding to w as consisting of a single edge. Lemma 4.4 : Let T be a graph labelled tree and G = G(T ).

(1) For each vertex x of S(T ), the set A(x) ∩ L T is not empty.

(2) Let x, y be distinct vertices of some component H. If xy is an edge of H, there is an alternating path between any leaf in A(x) and any leaf of A(y). Conversely, if an alternating path links a leaf in A(x) and a leaf of A(y), then this path goes through H, and more precisely, through x and y, and xy ∈ E H . Each component is isomorphic to an induced subgraph of G.

(3) Let uv be an edge of T . There is an alternating path between any leaf in A(x) where x is a neighbour of ρ u (uv) in H u and any leaf in A(y) where y is a neighbour of ρ v (uv) in H v . Any such path goes through the edge ρ u (uv)ρ v (uv).

Proof: (1) Let x belong to H u . Then x = ρ u (uv) for some (unique) edge uv of T . We use induction on the cardinality of N T,u\v , defined as the set of nodes of the connected component of Tu that contains v.

If N T,u\v = 1, then v is a leaf and A(x) = {v} = ρ v (uv) is a satisfying leaf.

Otherwise, H v has an edge ρ v (uv)y and then, y = ρ v (vw) for some edge vw of T . Then N T,v\w ⊂ N T,u\v and A(y) ∩ L T ⊆ A(x) ∩ L T . The set A(y) ∩ L T is not empty by induction, so is A(x) ∩ L T .

(2) Let xy = ρ u (uv)ρ u (uw) be an edge of component H u . Let z ∈ A(x) ∩ L T and z ′ ∈ A(y) ∩ L T . By connecting alternating paths between z and x, and z ′ and y with the edge xy, we get an alternating path between z and z ′ . Any such path must through xy as one checks from the definitions.

For each vertex x of H u , choose a vertex x of G in A(x) ∩ L T . By the previous observations, the induced subgraph of G whose vertices are the x's is isomorphic to H u .

(3) The proof is similar to that of (2).

The following corollary illustrates these notions in the basic case of trees.

Corollary 4.5 : G(T ) is a tree if and only if :

(1) each component of T is a tree, and

(2) if e = uv ∈ E T is not a pendant edge, then at least one of ρ u (e) and/or ρ v (e) is a leaf of, respectively H u and/or H v .

Proof : Assume G(T ) is a tree. By Lemma 4.4(2), each component of T is isomorphic to an induced subgraph of G(T ), hence is a tree since components are connected. For Property [START_REF] Bodlaender | Treewidth computations I. Upper bounds[END_REF], if none of ρ u (e) and ρ v (e) is a leaf, then the nodejoining of u and v (Definition 4.1(d)) merges H u and H v into a component that contains a complete bipartite graph K r,s such that r, s ≥ 2. This component has a cycle and G(T ) is not a tree by [START_REF] Bandelt | Distance-hereditary graphs[END_REF].

Conversely, let T satisfy ( 1) and [START_REF] Bodlaender | Treewidth computations I. Upper bounds[END_REF]. Consider e = uv satisfying Property (2) : if we apply to it the node-joining operation, the component H ′ w created in this way is still a tree. The obtained graph-labelled tree T ′ satisfies ( 1) and ( 2) and describes G(T ). By repeating this operation until all edges are pendant, we obtain a graph-labelled tree that defines G(T ) and that has one component that is a tree, all others being leaves. Hence G(T ) is a tree.

A tree may be be defined from several nonisomorphic graph-labelled trees. A stronger condition than (2) of Corollary 4.5, namely Condition (2) of Theorem 4.7, yields unicity, up to isomorphism, of the graph-labelled trees that define trees.

Definition 4.6 : The (canonical) split decomposition.

(1) A split of a graph G is a bipartition of V G into two sets V 1 and V 2 having each at least 2 vertices, such that the edges between V 1 and V 2 form a complete bipartite graph with at least one edge. Its bipartition is (A 1 , A 2 ) where

A 1 ⊆ V 1 and A 2 ⊆ V 2 . Hence, G is κ(G 1 ⊗G 2 ) for the induced subgraphs G 1 = G[V 1 ] and G 2 = G[V 1 ]
with appropriate labelling in D = {⊤, ⊥}: the vertices in A 1 ∪ A 2 are labelled by ⊤ and the others by ⊥.

(2) A graph is defined as prime 23 if it has at least 4 vertices and no split. The connected graphs with 3 vertices are stars S 3 and triangles (i.e., K 3 ). A star S n , n ≥ 3, has a center and n -1 adjacent vertices that are leaves (S n is a tree). Stars and cliques are not prime. A prime graph has actually at least 5 vertices. The cycles C n for n ≥ 5 are prime. Theorem 3 of [START_REF] Cunningham | Decomposition of directed graphs[END_REF], also proved as Theorem 2.9 in [START_REF] Gioan | Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF], states the following. Theorem 4.7 : Every connected graph with at least 3 vertices is G(T ) for a unique graph-labelled tree T such that :

(1) each component H v is singleton, or prime, or is a clique K n or a star S n , for some n ≥ 3,

(2) if e = uv ∈ E T , then H u and H v are not both cliques, and, if they are both stars, ρ u (e) and ρ v (e) are both centers or both leaves.

Unicity is understood up to isomorphism.

Such a graph-labelled tree is called the split decomposition of G. It can be obtained from an arbitrary graph-labelled tree that defines G by the nodesplittings and the node-joinings of Definition 4.1(d) (see [START_REF] Gioan | Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF] for details). The resulting tree has no node of degree 2 (cf. Remark 4.3). We will actually describe graphs by graph-labelled trees that need not be canonical.

Examples 4.8 : (1) The split decomposition of a clique K n , n ≥ 3, has a unique component that is a clique. But any graph-labelled tree all components of which are cliques defines a clique. A clique K n , n ≥ 3 can be defined by a graph labelled tree all components of which are triangles or isolated vertices. By using node splitting, we can replace a component K r+s+2 where r, s > 1 by two components K r+1 and K s+1 .

(2) In the split decomposition of a tree, all components are stars, and if e = uv ∈ E T , then ρ u (e) and ρ v (e) are both leaves of H u and H v by Corollary 4.5 and Theorem 4.7. Every tree with at least 3 nodes can be defined by a graph-labelled tree all components of which are stars S 3 or isolated vertices. As above, this can be achieved by node-splitting.

(3) A graph-labelled tree defines a DH graph if and only if all its components are stars and cliques ( [START_REF] Gioan | Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF], Section 3.1).

(4) The article [START_REF] Gioan | Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF] also studies particular DH graphs called 3-leaf powers. A 3-leaf power is a graph G defined as follows from a tree R : V G := L R and two vertices are adjacent if and only if they are at distance at most 3 in R. A graph is a 3-leaf power if and only if it is obtained from a tree by substitutions of cliques to its vertices [START_REF] Brandstädt | Structure and linear time recognition of 3-leaf powers[END_REF]. It follows that a graph G is a 3-leaf power if and only if it is a clique or is G(T ) for some graph-labelled tree T having one component, say H 0 , that is a tree and all others are cliques (an isolated vertex is a clique K 1 ). Hence, the set L of 3-leaf powers is defined, up to labels, by the two equations:

L = K ∪ Λ(L, L) K = ⊤ ∪ (K ⊗ K).
The set K is that of cliques where all vertices are live. The equation for L is derived from the first equation for rooted trees in Example 2.6(2). In the characterization of 3-leaf powers of [START_REF] Gioan | Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs[END_REF], the component H 0 that is a tree is decomposed in the canonical way of Theorem 4.7.

Graph-labelled trees and substitution operations.

We will use D-graphs, where D := {⊤, ⊥}. Definitions 4.9 : Rooted graph-labelled trees and related notions. (a) Let T be a graph-labelled tree, with underlying tree T , not reduced to a single node. Let us select a node r ∈ N T that is not a leaf and make it a root for T . We call then T a rooted graph-labelled tree.

(b) If u ∈ N T , we let

N u := {x ∈ N T | x ≤ T u} and V u := {x ∈ V G | x ≤ T u}. Hence, V r = L T , V u = {u} if u ∈ L T .
(2) A connected DH graph is defined by a graph-labelled tree T whose components are stars, cliques and single vertices. By means of node splittings (Definition 4.1(d)), we can transform T into a graph-labelled tree whose components are stars S 3 , triangles K 3 , together with one component 24 K 2 : for n ≥ 4, a component (isomorphic to) K n can be split into K 3 and K n-1 , and a component S n can be split into S 3 and S n-1 where the center of S 3 is linked to a leaf of S n-1 .

Let us take as root the component K 2 . We obtain from Theorem 4.11 the following equations for defining these graphs :

S = κ(⊤) ∪ κ(U ⊗ U ), U = ⊤ ∪ (U ⊕ U ) ∪ (U ⊗ U ) ∪ Λ(U, U ),
that are the two equations of Proposition 2.7(2).

Clique-width bounds from graph-labelled trees Theorem 4.13 : Let G be a connected graph defined by rooted graph labelled tree T such that each operation σ[H ′ u , x 1 , ..., x p ] has width at most k.

Then cwd ⊥ (G) ≤ k and cwd(G) ≤ k + 1.
Proof: Immediate consequence of Proposition 3.2 and Theorem 4.11.

The next lemma gives an upper-bound to the widths of the terms in

T ⊥ (F C ) that define the D-graphs H ′ u . Lemma 4.14 : Let H be a D-graph of clique-width k. Then cwd ⊥ (H) ≤ k + min{k, V live H , V dead H }.
Proof: That cwd ⊥ (H) ≤ 2k follows from Lemma 1.3. This lemma uses a partition of the vertex set in two parts. At the end of the construction, all vertices of one part are relabelled into ⊥.

For proving that cwd ⊥ (H) ≤ k + V live H , we consider a term that defines H with a set C ′ of k labels different ⊥. Assume that V live H = {x 1 , ..., x p }. We add labels c 1 , ..., c p to C ′ such that c i will only label x i .

We transform t into t ′ accordingly. In particular, to take a typical case, if at some position in t the operation add a,b adds edges between x i , labelled at this point by a (there may be other a-labelled vertices) and b-labelled vertices, then we replace it by add ci,b • add a,b . Hence, we can use p + k labels different from ⊥.

If V dead H = {x 1 , ..., x p }. We do a similar construction.

Theorem 4.15 : Let G be defined by a canonical graph-labelled tree T whose components have maximal clique-width m and maximal degree d, then m ≤ cwd(G) ≤ m + min{m, d} + 1.

Proof : The inequality m ≤ cwd(G) follows from Lemma 4.4(2) since cliquewidth is monotone with respect to the induced subgraph relation.

We now prove the other inequality. For each component H u , the number of live vertices in H ′ u is at most d. Hence, Lemma 4.14 gives cwd ⊥ (H ′ u ) ≤ m + min{m, d}. Then, Theorem 4.13 gives cwd ⊥ (G) ≤ m + min{m, d} hence, cwd(G) ≤ m + min{m, d}+1.

Remark 4.16 : If G is a tree that is not a star and is defined by T whose components are stars with three nodes, hence of clique-width 2, we have m = 2 and cwd(G) = 3.

Parity graphs.

A graph is a parity graph if for any two vertices, the induced paths joining them have the same parity. DH graphs and bipartite graphs are parity graphs. The article [START_REF] Cicerone | On the extension of bipartite to parity graphs[END_REF] establishes that parity graphs are those with a split decompositions whose components are cliques and bipartite graphs. We do not get a finite grammar as bipartite graphs, whence also parity graphs, have unbounded clique-width.

Rank-width.

Rank-width is another complexity measure initially defined for undirected graphs 25 , denoted by rwd(G). As tree-width and clique-width, it is based on a tree-structuring of the given graph G. The DH graphs are those of rank-width 1 [START_REF] Oum | Rank-width and vertex-minors[END_REF]. Rank-width is related to clique-width by the inequalities rwd(G) ≤ cwd(G) ≤ 2 rwd(G)+1 -1. Furthermore, if G = G(T ) for some graph-labelled tree T , and m is the maximal rank-width of a component H u , then rwd(G) = m (Theorem 4.3 of [START_REF] Hlinený | Width parameters beyond tree-width and their applications[END_REF]). Hence, if cwd(H u ) ≤ m for all u, we get rwd(G) ≤ m and cwd(G) ≤ 2 m+1 -1. The bound given by Theorem 4.15 is thus better.

Directed graphs

We now extend our results to directed graphs. We recall that Cunnigham defines in [START_REF] Cunningham | Decomposition of directed graphs[END_REF] a canonical split decomposition for directed graphs that are strongly connected (Theorem 1). An undirected graph can be seen as a directed one where each edge has an opposite one. It is connected if and only if the corresponding directed graph is strongly connected. Hence, Theorem 4.7 is a special case of a more general one for directed graphs 26 .

We use again graph-labelled trees and split decomposition graphs as in [START_REF] Courcelle | The monadic second-order logic of graphs XVI : Canonical graph decompositions[END_REF]. In order to extend to directed graphs the results of Section 4, we will revise the notion of substitution of Section 2 for graphs with labels that encode edge directions. In some sense, the set of live vertices is partitioned into three sets, designated by the tags ⊤, +, -, attached to the labels of the sets C used to construct graphs.

In this section, all graphs are directed unless otherwise indicated. However, the graphs representing graph-labelled trees have undirected edges as well as directed ones.

Definition 5.1 : Substitutions. We let D be the set of labels {⊥, ⊤, +, -} ordered in such a way that ⊥ < + < ⊤, ⊥ < -< ⊤ and + andare incomparable. Let K be a D-graph with vertex set {x 1 , . . . , x p } and H 1 , . . . , H p be pairwise disjoint D-graphs, that are disjoint from K. We define a D-graph G as follows:

G := K[H 1 /x 1 , . . . , H p /x p ] where V G := V H1 ⊎ . . . ⊎ V Hp , π G (v) := inf{π Hi (v), π K (x i )} if v ∈ V Hi , its (directed) edges are as follows, for u, v ∈ V G :
uv ∈ E G if and only if :

uv ∈ E Hi for some i, or π Hi (u) ∈ {⊤, +}, π Hj (v) ∈ {⊤, -} and x i x j ∈ E K (and so i = j). We obtain graph operations, as in Section 2, that we will use to describe the directed graphs defined by graph-labelled trees. Definition 5.2: Graph operations based on substitution. For each D-graph K with vertex set enumerated as {x 1 , . . . , x p }, we define as follows a p-ary operation on D-graphs denoted by σ[K, x 1 , . . . , x p ] : 3 where H 1 , . . . , H p are pairwise disjoint and disjoint from K. If they are not, we replace them by isomorphic copies, so that σ[K, x 1 , . . . , x p ] becomes a p-ary operation on abstract D-graphs.

σ[K, x 1 , . . . , x p ](H 1 , . . . , H p ) := K[H 1 /x 1 , . . . , H p /x p ]
If we extend Definition 5.1 so that K has other vertices than x 1 , . . . , x p , then the properties of Proposition 2.2 are still valid.

Substitutions as derived operations

Clique-width is defined for directed graphs with the help of the operations --→ add a,b that create directed edges from a-labelled vertices to b-labelled ones. Our objective is to bound the clique-width of G := K[H 1 /x 1 , . . . , H p /x p ] as O(max{cwd(K), cwd(H 1 ), . . . , cwd(H p )}).

Definitions and notations 5.3. We consider G := K[H 1 /x 1 , . . . , H p /x p ].

(a) The graphs G, K, H 1 , . . . , H p are D-graphs that we will define by terms t G , t K , ... in T (F E ) where E ⊂ C×D×D, in such a way that G = relab f (val(t G )), where f((a, α, β)) := β for all (a, α, β) in E, and similarly for K, H 1 , . . . , H p , with the same function f . More precisely, we will use (b) Let K ≃ val(t) for some term t K ∈ T (F C ). (The labels in C do not specify the labelling π K : V K → D). Let x 1 , . . . , x p be the vertices of K. Each vertex x i is defined by a nullary symbol a i (x i ) in t. We construct a term t K in T (F E , {u 1 , . . . , u p }) as follows :

E := {(a, α, β) | a ∈ C, α, β ∈ D, β ≤ α}.
-we replace each a i (x i ) by the variable u i , -we replace each operation relab h by relab h where h((a, α, β)) := (h(a), α, β) for all (a, α, β) ∈ E, (a, ⊤, ⊤), (a, ⊤, +), (a, ⊤, -), (a, ⊤, ⊥), (a, +, +), (a, +, ⊥), (a, -, -), (a, -, ⊥), for all a ∈ C. By using this remark, we obtain: Proposition 5.5 : If a graph G is defined up to vertex labels by a composition of operations σ[K, x 1 , . . . , x p ] such that each graph K has clique-width at most k, then, cwd(G) ≤ 8k + 1.

Proof : Let G be defined by a term over operations σ[K, x 1 , . . . , x p ] such that cwd(K) ≤ k, and, of course, nullary symbols. The terms t K can be written with the labels of a set C of k labels; as nullary symbols one can use the single one c.

By composing the terms t K and the relabellings h i according to Lemma 5.4, we obtain a term that defines G by using only 8k + 1 labels. Hence, cwd(G) ≤ 8k + 1.

Directed graph-labelled trees. Definition 5.6 : Graph-labelled trees describing directed graphs. In the following definition, unspecified definitions and notation are as in Definition 4.1. We avoid repetions as much as possible.

(a) A directed graph-labelled tree, denoted by T is an undirected tree T with at least 3 nodes, that is equipped, for each node v ∈ N T , with a directed graph H v , called a component, and a bijection ρ v : Inc T (v) → V Hv . Components are pairwise disjoint and need not be connected, see Remark 5.7(2) below. If v is a leaf, then H v has a single vertex that we identify with v.

(b) We define S(T ) as the graph consisting of the union of the components together with the undirected edges ρ u (e)ρ v (e) for e = uv, (cf. Figure 4). The directed edges are those inside the components. A path, or a walk 27 , in S(T ) from x to y is alternating if no two consecutive edges are in a same component and all edges belonging to components are directed from x to y. There is at most one alternating path from x to y, but there may exist also one from y to x. This is the case if and only if each directed edge zz ′ on this path has an opposite edge z ′ z.

To be more precise, we define for a vertex x of a component H u , A -(x) as the set of vertices of S(T ) accessible from x by an alternating path whose first edge is not in H u , and A + (x) as the set of vertices w of S(T ) such that there is an alternating path from w to x whose last edge is not in H u .

(c) The graph described by T , denoted by G(T ), has vertex set L T (the set of leaves of T ) and an edge uv if and only if there is an alternating path from Figure 4: A directed graph-labelled tree T . u to v. If there is a path u 1 → u 2 ... → u p in G(T ), the concatenation of the alternating paths corresponding to the edges u i u i+1 forms an alternating walk from u 1 to u p .

(d) The node-joining operation (called elimination of an edge e of T in [START_REF] Courcelle | The monadic second-order logic of graphs XVI : Canonical graph decompositions[END_REF]) is defined as follows. If e = uv is an edge between two internal nodes of T , its contraction fuses u and v into a single node say w, giving tree T ′ , and replaces the graph

H u ⊎ H v by H ′ w := (H u ⊎ H v ) -{ρ u (e)
, ρ v (e)} augmented with an edge from any vertex x in H u to any vertex y in H v such that xρ u (e) ∈ E Hu and ρ v (e)y ∈ E Hv . We obtain a directed graph-labelled tree T ′ that describes the same graph : this is easy to check by considering alternating paths. By iterating as much as possible this elimination step, we obtain a star whose central component is isomorphic to G(T ).

The opposite transformation called node-splitting also preserves the defined graph.

The notion of canonical decomposition for strongly connected (directed) graphs (Theorem 2 of [START_REF] Cunningham | Decomposition of directed graphs[END_REF]) uses cliques, stars and particular graphs called cycles of transitive tournaments that have clique-width at most 4 (by Proposition 4.16 of [START_REF] Courcelle | The monadic second-order logic of graphs XVI : Canonical graph decompositions[END_REF]). We will not use this difficult notion. We will describe directed graphs by directed graph-labelled trees, either canonical or not. Our results will be valid even if some components are not connected.

Examples 5.7 : (1) Figures 4 shows a directed graph-labelled tree T and Figure 5 the corresponding graph G(T ). The double arrow in the components H x and H u indicate pairs of opposite directed edges. For a comparison with Figure 1, there is no alternating path between 2 and 7, in either direction. Hence, these two vertices are not adjacent in G(T ).

"central" strongly connected component and leaves. This component is isomorphic to G, hence G is strongly connected. Proposition 5.9 : Let G be defined by a graph-labelled tree T . Then G is strongly connected if and only if all components of T are strongly connected.

Proof : The "if" direction is proved in the previous proposition. For the converse, let x and y be distinct vertices of a component H u . Let s ∈ A + (x)∩L T and t ∈ A _ (y) ∩ L T . There is a path in G from s to t. Each edge of this path corresponds to an alternating path in S(T ) whose directed edges are oriented from s to t. The concatenation of these paths is a walk 28 in S(T ). It is not necessarly a path because some undirected edges may be traversed twice. (In the example of Figure 4 the path 2 -→ 6 -→ 7 -→ 4 comes from a walk that traverses twice the edge between H u and H w ). This walk must enter H u first via x and exit it last via y. Its edges belonging to H u form a directed path from x to y. Hence, H u is strongly connected.

Remark 5.10 : Even if G(T ) is strongly connected, some components of T may not be isomorphic to induced subgraphs of G(T ) (by contrast with Lemma 4.4(2)). Consider for an example a directed graph-labelled tree having two internal components isomorphic to the directed cycles -→ C 3 . It defines -→ C 4 that does not contain -→ C 3 as an induced subgaph. We will compare below the clique-widths of a graph and its components.

Directed graph-labelled trees and substitution operations.

We will use the set of labels D := {⊥, +, -, ⊤}. if u = r, then H ′ r := H r , and all its vertices are dead ; otherwise, we define H ′ u := H uu where a vertex x is labelled as follows : its label is

⊤ if xu, ux ∈ E Hu , it is + if xu ∈ E Hu and ux / ∈ E H u , it is -if ux ∈ E H u and xu / ∈ E H u ,
-v x -→ v ′ x -w ′ x ←-w x -x.
Then G(T ) consists of the isolated vertices x. For strongly connected graphs, we have a better situation. Proposition 5.14 : There is a function f such that cwd(H) ≤ f (cwd(G)) whenever G is strongly connected and H is a component of some directed graphlabelled tree that defines it.

We need some definitions. An edge xy of a graph G is special if x has outdegree 1 and y has indegree 1. Let F be a set special edges. A path with all its edges in F is called an F -path. The graph G\F, obtained from G by contracting the edges of F is defined as follows, where X is the set of terminal ends of the edges of F :

V G\F := V G -X,
xy ∈ E G\F if and only if x, y / ∈ X and, either xy ∈ E G or there exist a vertex z such that zy ∈ E G and an F -path from x to z.

If F forms a directed cycle (necessarly disconnected from G -X), then V G\F = G -X.
Lemma 5.15 : There is a function f such that cwd(G\F ) ≤ f (cwd(G)) for every directed graph G and every set F of special edges.

Proof : There exists a monadic second-order transduction (not using edge set quantifications) that maps the pair (G, X) of a graph G and a set X that is the set of terminal ends of the edges of a set F of special edges (uniquely determined from X) to G\F . Its definition is a straightforward translation from the definition.

The existence of f follows from of Corollary 7.38(2) of [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF].

However, the proof does not give a good bound 29 for f . It is an open question whether cwd(G\F ) ≤ cwd(G) or even 30 cwd(G\F ) = O(cwd(G)).

Proof of Proposition 5.14: Let G be strongly connected defined by some graph-labelled tree T . Let H u be any component not reduced to a single vertex. We claim that there exists an induced subgraph G ′ of G such that H u is isomorphic to G ′ \F for some set F of special edges.

Let x := ρ u (uv).

2 9 For a comparison, if an undirected graph H is obtained from G by erasing degree 2 vertices, that is by contracting a set of edges that have all an end vertex of degree 2, then cwd(H) ≤ 2 cwd(G)+1 -1 (Proposition 2 of [START_REF] Courcelle | Clique-width and edge contraction[END_REF]). However, we prove in [17] that cwd(H) > 2 cwd(G)/4 in some cases.

3 0 We can prove that clique-width is not increased when a path of special edges from x to y is contracted into an edge xy. Otherwise, we can bound cwd(G\F ) by using f (k) =: k 2 .3 k-1 [17].

Case 1 : There exists a vertex z of G belonging to A + (x) ∩ A -(x) ∩ L T . We choose one that we denote by x := z.

Case 2 : Otherwise, H v has at least 3 vertices. Let x ′ := ρ u (uv). Then H v contains a directed cycle going through x ′ that does not consist of two opposite edges incident to x ′ , otherwise we are in Case 1. Hence there are edges x ′ y, y ′ x ′ and a directed path from y to y ′ that avoids x ′ . Let z ∈ A -(y) ∩ L T and z ′ ∈ A + (y ′ ) ∩ L T . There is a path in G from z to z ′ . Each of its edges corresponds to an alternating path in S(T ). By concatenating these paths, one gets an alternating walk, all vertices of which are in N T,u\v . We let P x be such a path in G and we denote z by x 1 and z ′ by x 2 . The paths P x are pairwise disjoint.

Let X be the union of the vertex sets of the paths P x for x ∈ V H u together with the vertices x. Let G ′ := G[X] and F be the set of edges of the paths P x . They are special edges of G ′ because the paths are pairwise disjoint.

Let H := G ′ \F . The two end vertices x 1 and x 2 of a path P x get fused into a single vertex that we denote by x. The vertex set of H is thus { x | x ∈ V Hu }.

Claim: The bijection x -→ x is an isomorphism H → H u . Proof of the claim: Let xy be an edge of H u . Assume x is in Case 1 and y in Case 2. We have alternating paths from x to x and from y to y 1 , and one from x to y 1 . Hence we have an edge in G from x to y 1 . We have the edge x y in H. The proofs are similar for the three other cases (x in Case 2, y in Case 2 etc.).

Conversely, assume that we have an edge x y in H. Then, we have x = ρ u (uv) and y = ρ u (uw) with v = w. There are four cases, e.g., x is in Case 1 and y in Case 2. Then, we get easily that xy is an edge of H u by considering alternating paths.

This completes the proof of the proposition because cwd(G ′ ) ≤ cwd(G).

Remarks 5.16 : (1) By the recent result in [17], we can use the mapping f(k) =: k 2 .3 k-1 to bound the clique-widths of components.

(2) The proof of Proposition 5.14 given in [START_REF] Courcelle | The monadic second-order logic of graphs XVI : Canonical graph decompositions[END_REF] (as Proposition 4.16) is incorrect: Lemma A.2.3 shows (correctly) that cwd(H) ≤ 4cwd(G) if H is obtained from G by fusing two vertices. But, in order to prove the statement, one must fuse the vertices of several pairs (as we do above to define H from G ′ ), hence, one does not obtain a bounding function f as claimed.

An alternative split decomposition for directed graphs.

Kanté and Rao have defined in [START_REF] Kanté | Directed rank-width and displit decomposition[END_REF] the displit decomposition of a directed graph. For an undirected graph, it is the same as the split decomposition. It is incomparable to the split decomposition of [START_REF] Cunningham | Decomposition of directed graphs[END_REF] because the prime components are different. However, every connected directed graph has a unique decomposition.

Furthermore, for an appropriate notion of rank-width for directed graphs [START_REF] Kanté | The rank-width of edge-coloured graphs[END_REF], they obtain that the rank-width of a graph is the least upper-bound of the rank-widths of the components of its displit decomposition (cf. Remark 4.16). They also characterize the directed graphs of rank-width at most 1 in a way that generalizes the various characterizations of distance-hereditary graphs (in particular that of [START_REF] Oum | Rank-width and vertex-minors[END_REF]).

We think that the results of this section and of [START_REF] Courcelle | The monadic second-order logic of graphs XVI : Canonical graph decompositions[END_REF] (the existence of monadic second-order transformations between directed graphs and their canonical split decompositions) can be extended to displit decompositions.

Conclusion

Our purpose was to clarify the relations between split-decompositions for directed and undirected graphs, substitutions and the related graph grammars, and to obtain good bounds on the clique-widths of the defined graphs. For doing that we had to generalize the notion of substitution used in the theory of modular decomposition (cf. Definitions 2.1 and 5.1).

Our open questions concern bounds on the clique-widths of graphs defined by edge-contractions : see Lemma 1.3, Theorem 4.15 and Theorem 5.13. (Results will appear in [17]).

Definition 1 . 2 :

 12 Clique-width (a) We define the following operations on C-graphs : -the union of two disjoint C-graphs is denoted by the binary function symbol 7 ⊕, -the unary operation add a,b for a, b ∈ C, a = b that adds an undirected edge between each a-labelled vertex x and each b-labelled vertex y (unless there is already an edge xy); for building directed graphs, we use similarly --→ add a,b to add directed edges from a-labelled to b-labelled vertices,

Figure 2 :

 2 Figure 2: The graph G(T ).

Lemma 5 .

 5 12 motivates this definition. If we consider an undirected graph as a directed graph where each edge has an opposite one, and vertices are labelled by ⊥ or ⊤, then Definition 5.1 gives the same notion of substitution as Definition 2.1. Example : Let K be x -→ y ←→ z. where the labels of x, y and z are respectively +,and ⊤. Let X be the edgeless D-graph ⊥(0) ⊕ +(1) ⊕ -(2) ⊕ ⊤(3) (its vertices 0,1,2,3 are labelled respectively by ⊥, +, -, ⊤). Let similarly Y := +(4) ⊕ -(5) ⊕ ⊤(6) and Z := +(7) ⊕ -(8) ⊕ ⊤(9).The graph K[X/x, Y/y, Z/z] is shown in Figure 3. The labels of vertices 0,1,5,7,8 and 9 are as in X, Y and Z. Those of 2,3,4 and 6 are respectively ⊥, +, ⊥ andbecause of the inf operator in Definition 5.1(a).

Figure 3 :

 3 Figure 3: Figure 3

  (The set D is ordered, cf. Definition 5.1).

Definitions 5 . 11 :

 511 Rooted graph-labelled trees and related notions. (a) Let T be a directed graph-labelled tree, with underlying tree T and G := G(T ). Let us select a node r ∈ N T -L T and make it a root for T . If u ∈ N T , then V u is as in Definition 4.9.(b) The leader of a component H u such that u is not the root is the vertex ρ u (wu) denoted by u, where w is the father of u. If u ∈ N T -L T , we define a D-graph H ′ u as the follows :

  and it is ⊥ if xu and ux are not in E Hu .We build T with any connected graph H as "root" component. Attach to each vertex x of H a path of the form x

In[START_REF] Meister | Clique-width with an inactive label[END_REF], such vertices are defined in clique-width terms by inactive labels. We will use ⊥ as inactive label in Sections 3 and

[START_REF] Chang | Dynamic programming on distance-hereditary graphs[END_REF] A different notion of split decomposition for directed graphs, that generalizes also the one for undirected graphs, has been defined in[START_REF] Kanté | The rank-width of edge-coloured graphs[END_REF]. We will say a few words about it at the end of Section 5.

This characterization is from[START_REF] Bandelt | Distance-hereditary graphs[END_REF]. The DH graphs are also the graphs of rank-width 1[START_REF] Oum | Rank-width and vertex-minors[END_REF]. They have clique-width at most 3, as we will prove in detail.

As ⊕ is associative, we will write t = t 1 ⊕ t 2 ⊕ ... ⊕ tn instead of t 1 ⊕ (t 2 ⊕ (... ⊕ tn)...).

If h only changes a into b, we denote relab h by relab a→b and call this operation an elementary relabelling. By using only elementary relabellings, we obtain the same notion of clique-width ([14], Proposition 2.118).

Vertices are taken from a fixed countable set.

0 In[START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], we denote cwd * by cwd. 1 1 The construction is similar for directed graphs and it needs no more labels. 1

It not hard to prove that lcwd(G) ≤ lcwd(Gx) + 2 where lcwd denotes the linear clique-width. This variant is defined by requiring that at least one of the two arguments of an operation ⊕ is a nullary symbol. See e.g.,[14,

[START_REF] Heggernes | Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs[END_REF].1 3 A lower-bound is established in[17]. .

[START_REF] Brandstädt | Structure and linear time recognition of 3-leaf powers[END_REF] It is actually enough to assume that(V H 1 ⊎ . . . ⊎ V Hp ) ∩ (V K -{x 1 , . . . , xp}) = ∅.

[START_REF] Chang | Dynamic programming on distance-hereditary graphs[END_REF] We use the notation σ[K, v 1 , . . . , v p ] for the function symbol and the corresponding operation.

[START_REF] Cicerone | On the extension of bipartite to parity graphs[END_REF] See Example

2.5[START_REF] Bandelt | Distance-hereditary graphs[END_REF] for the solution of equations in sets of terms. In the proof, we will identify W and L(W ) without risk of difficulty.1 7 We use here the footnote in Definition 2.1.

8 from[START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF], Section

2.11 9 This term uses an auxiliary label a to define graphs of type {⊤}. This label does not appear in the type. It can be replaced by any other one different from ⊤.

0 These limitations on the use of ⊥ make it an inactive label in[START_REF] Meister | Clique-width with an inactive label[END_REF]. 2 1 This is clear from Definition 2.1.

[START_REF] Bodlaender | Treewidth computations I. Upper bounds[END_REF] If some components are not connected, the defined graph is not connected. Disconnected graphs are best described through their connected components. Hence, we assume that all components are connected. In Section 5, we will allow components that are not connected for directed graphs.

[START_REF] Bouvier | Graphes et décompositions[END_REF] A different notion of prime graph is used in the theory of modular decomposition.

4 By Remark 4.3.

[START_REF] Chang | Dynamic programming on distance-hereditary graphs[END_REF] Extension to directed graphs is in[START_REF] Kanté | The rank-width of edge-coloured graphs[END_REF].2 6 We thought better to begin with undirected graphs, because the formal setting is simpler and most graph structure theory and graph algorithms concern undirected graphs.

[START_REF] Courcelle | An axiomatic definition of context-free rewriting and its application to NLC graph grammars[END_REF] A walk is like a path but it can go several times through a vertex.

[START_REF] Courcelle | The monadic second-order logic of graphs XVI : Canonical graph decompositions[END_REF] A vertex may occur several times on a walk.

This work has been supported by the French National Research Agency (ANR) within the IdEx Bordeaux program "Investments for the future", CPU, ANR-10-IDEX-03-02, and also within the project GraphEn started in October 2015.

(c) If u ∈ N T has father w, we say that ρ u (wu) is the leader of H u , denoted by u, and we define H ′ u as the D-graph H u -u where a vertex x live (labelled by ⊤) if it is adjacent to u in H u and is dead (labelled by ⊥) otherwise. Otherwise, u is the root r and H ′ r := H r , all its vertices being defined as dead. (d) If u ∈ N T , we define G u as G[V u ] labelled as follows:

(d.1) if u = r, then every vertex of G u = G is labelled as dead, (d.2) if u = r, a vertex y of G u is labelled by ⊤ if it is in A(z) for some neighbour z (in H u ) of the leader of H u ; otherwise, it is labelled by ⊥.

Example : Consider the graph-labelled tree of Figure 1 with root x. The vertices 4 and 5 are live in G v , but not in G u (so is 3). The vertices 2,6,7 are live in G u .

The following lemma relates graph-labelled trees and substitution operations. Note that the graphs H ′ u depend on the root that is chosen.

Lemma 4.10 : Let T be a graph-labelled tree that defines G. If u ∈ N T -L T has sons u 1 , ..., u p , and the corresponding p vertices of H ′ u are x 1 , ..., x p (that is,

are the vertex sets of the graphs G ui . Hence, G u and K have the same vertices.

2) As the graphs G w are induced subgraphs of G, two vertices of G ui are adjacent in G u if and only if they are in G as well as in G ui , hence also in K.

Consider vertices x of G u i and y of G u j , j = i. If they are adjacent in G u , hence in G, they are linked by an alternating path, that must go through H u (and not through its leader) and use its edge ρ u (u i u)ρ u (u j u) = x i x j , an edge of H ′ u . This path goes through the leader

Conversely, if xy ∈ E K , then x i x j is an edge of H ′ u , the vertex x is live in G ui and y is live in G uj . Going back to definitions, we have an alternating path between x and y. Hence, xy is a edge of G hence of G u .

3) If u is the root, all vertices of H ′ u are dead, hence, so are those of K, as well as those of G = G r .

Otherwise, let x be a vertex of G ui that is live. Hence, there an alterning path P between x and the leader

It is also in G u because P can be extended into an alterning path from x to z. If ρ u (u i u) = x i is not a neighbour of z, then x is dead in K. It is also in G u because P cannot be extended into an alterning path from x to z.

If x is not live in G u i , then it is not in K, and is not either in G u , because otherwise, the alternating path between x and z would give a path P as above.

From graph-labelled trees to grammars

If M is a finite set of connected (unlabelled) graphs having at least 2 vertices. We define G(M) as the set of graphs described by graph-labelled trees whose components are in M. For each H ∈ M and x ∈ V H , we define H\x as the D-graph Hx where the neighbours of x are labelled by ⊤ and the others by ⊥, hence are defined as dead. Note that Hx need not be connected. The labelled graph H ′ u of Definition 4.9 is H u \u. In the following theorem, σ denotes operations σ[H, x 1 , ..., x p ] for H ∈ M, where all vertices of H are dead, and σ ′ operations σ[H\x, x 1 , ..., x p ] for H ∈ M and x ∈ V H . Theorem 4.11 : If M is a finite set of connected graphs having at least 2 vertices, then G(M) is the set S defined by the two equations :

Otherwise, it is defined by a finite term t = σ(t 1 , ..., t p ) where t 1 , ..., t p are terms over ⊤ and the operations σ ′ . By Lemma 4.10, this term represents a rooted graph labelled tree T . The component at the root is isomorphic to H such that σ = σ[H, x 1 , ..., x p ]. The terms t 1 , ..., t p represent the subtrees of T issued from the p sons of the root. Hence, G is described by a rooted graph-labelled tree with components in M. Hence G ∈ G(M).

Let conversely G ∈ G(M). If it is a dead isolated vertex, then it is in S, defined by κ(⊤). Otherwise it is defined by a rooted graph-labelled tree T , hence, by a term t = σ(t 1 , ..., t p ) as above. The subtrees of T issued from the sons of the root are defined by the terms t 1 , ..., t p .

Examples 4.12 : (1) We examine some of the operations σ[H, x 1 , ..., x p ] and σ[H\x, x 1 , ..., x p-1 ] that arise in split decompositions, in particular, in the canonical ones.

Case 1 : H or H\x is a clique K p , p ≥ 1, all vertices being live. Then, we have :

Case 2 : H = S p , p ≥ 3, with center x 1 , that is live in S p \x p , all other vertices being dead. We have :

Case 3 : H = S p , p ≥ 3, with center x p . Then, all vertices of S p \x p are live and we have :

-we replace each operation --→ add a,b by the composition (in any order) of the operations --→ add (a,α,β),(b,α ′ ,β ′ ) such that α ∈ {⊤, +}, α ′ ∈ {⊤, -} and β, β ′ ∈ D. Furthermore, for each i := 1, ..., p, we define

With these definitions and notation, we have :

These two graphs have the same vertex set,

because the relabellings in t K do not modify the third components of labels. It is same in G by Definition 5.1.

We now compare the edges of G and of

∈ E Hi , it is not an edge of G either. And it is not an edge of G ′ because the labels of u and v have the same first components in relab hi (t i ) and the relabellings in t K maintain this equality. Hence, no edge between u and v is created by the operations

If uv ∈ E G , then x i x j is an edge of K and the labels of u and v in H i and H j are respectively α ∈ {⊤, +} and α ′ ∈ {⊤, -} by Definition 5.1.

Let us now consider G ′ . At some position w in t K the edge x i x j is created by an operation --→ add a,b . In val(relab hi (t i )) and val(relab hj (t j )), the labels of u and v are respectively (a i , α, β) and (a j , α ′ , β ′ ). for some β and β ′ , and, in t K , a i and a j are relabelled into a and b at position w. The labels of u and v are thus (a, α, β) and (b, α ′ , β ′ ) in t K at the position p ′ corresponding to p. Hence, uv is an edge of G ′ , created by --→ add (a,α,β),(b,α ′ ,β ′ ) at p ′ . Hence every edge of G is an edge of G ′ . The proof is similar in the other direction. Hence, G = G ′ .

No label (a, ⊥, ⊥) occurs in an edge addition operation of t K . Furthermore, f((a, ⊥, ⊥)) = ⊥ for each a ∈ C. Hence, all labels (a, ⊥, ⊥) can be replaced by the unique label (c, ⊥, ⊥) for some fixed c ∈ C. It follows that t K and the relabellings h i only use the following 8 |C| + 1 labels : 4 (2) A directed graph-labelled tree may define a disconnected graph although its components are connected. As a small example, consider S(T ) defined as xz ′ -→ zu ←u ′y: its internal components are z ′ -→ z and u ←u ′ . Then G(T ) consists of the two isolated vertices x and y. Eliminating the edge between the two internal components yields a component consisting of two isolated vertices u ′ and z ′ . Proposition 5.8 : Let G be defined by a directed graph-labelled tree T whose components are strongly connected.

(1) For each vertex x of S(T ), we have

(3) G is strongly connected.

Note that T has at least two leaves and so, that G has at least two vertices.

Proof : (1) Let x be a vertex of a component H u . Hence, x = ρ u (uv) for some node v. We use induction on the cardinality of N T,u\v (cf. the proof of Lemma 4.4(1)). If it is 1, then v is a leaf and

Otherwise, we have in H v an edge zy such that y = ρ v (uv) and z = ρ v (vw) for some edge vw of T . We have N T,v\w ⊂ N T,u\v , hence, by induction,

(2) Just consider alternating paths, as in the proof of Lemma 4.4.

(3) The node-joining operation preserves the strong connectedness of the components as one checks from Definition 5.6(d). By repeating this operation, one obtains a directed graph-labelled tree that defines G and consists of one Note that the graphs H ′ u depend on the chosen root r. Otherwise, a vertex x has label ⊤ if there are alternating paths from x to u and from u to x; it has label + if there is an alternating path from x to u and no such path from u to x; it has labelif there is an alternating path from u to x and no such path from x to u and label ⊥ if there are no alternating paths between x and u.

The following lemma extends Lemma 4.10.

Lemma 5.12 : If u ∈ N T -L T has sons u 1 , ..., u p and the corresponding p vertices of H ′ u are x 1 , ..., x p (that is,

As in Lemma 4.10, the vertex sets of G u and K are the same and the edges of G ui are the same as in G u and K.

We consider x in G u i and y in G u j , j = i. If xy is an edge of G, there is an alternating path from x to y. It must go through H u (and not through its leader) via the (directed) edge ρ u (u i u)ρ u (u j u) = x i x j in H ′ u . This path goes through the leader ρ u i (u i u) of H u i . Hence, x is live in G u i . More precisely, it has label + or ⊤. Similarly, y has labelor ⊤ in G uj . Hence xy is an edge of K.

Conversely, if xy ∈ E K , then x i x j is an edge of H ′ u , x has label + or ⊤ in G ui and y has labelor ⊤ in G uj . Going back to definitions, we have an alternating path from x and y built from alternating paths from x to x i , and x j to y and the edge x i x j . Hence, xy is a edge of G, hence of G u .

It remains to compare the vertex labels in K and in G u . Let x be a vertex of G u i labelled by + in G u . There is an alternating path from x to the leader u of H u and no such path from u to x. Hence, there is an alternating path from x to u i and an edge in H u from ρ u (uu i ) to u. Hence the label of ρ u (uu i ) is either + or ⊤. The label of x in G ui is either either + or ⊤, hence its label in K is either + or ⊤. If it would be ⊤, we would have an edge in H u from u to ρ u (uu i ) and an alternating path from u to x and x would have label ⊤ in G u . Hence x has label + in K.

The proofs are similar for the other labels.

Theorem 5.13 : Let G be defined by directed graph-labelled tree T whose components have clique-width at most k. Then cwd(G) ≤ 8k + 1.

Proof: From Proposition 5.5 and Lemma 5.12, along the lines of Theorem 4.11.

One can define a graph-labelled tree T that has components of arbitrary large clique-width but defines a graph without edges, hence of clique-width 1.