Alessandra Cherubini
email: alessandra.cherubini@polimi.it

Andrzej Kisielewicz

Brunetto Piochi
email: piochi@math.unifi.it

On the Length of Shortest 2-Collapsing Words

Keywords: property ∆ k, finite automata, synchronizing finite automata

Given a word w over a finite alphabet Σ and a finite deterministic automaton A = Q, Σ, δ , the inequality |δ(Q, w)| ≤ |Q|k means that under the natural action of the word w the image of the state set Q is reduced by at least k states. The word w is k-collapsing (k-synchronizing) if this inequality holds for any deterministic finite automaton (with k + 1 states) that satisfies such an inequality for at least one word. We prove that for each alphabet Σ there is a 2collapsing word whose length is |Σ| 3 +6|Σ| 2 +5|Σ| 2 . Then we produce shorter 2-collapsing and 2-synchronizing words over alphabets of 4 and 5 letters.

1 Introduction and preliminaries.

In this paper by an automaton A = Q, Σ, δ we mean a finite deterministic automaton with state set Q, input alphabet Σ, and transition function δ : Q × Σ → Q. The action of Σ on Q given by δ will be denoted by concatenation: qa = δ(q, a). This action extends naturally, by composition, to the action of the words of Σ * on Q. Given a word w ∈ Σ * , we will be interested in the difference of the cardinalities |Q| -|Qw|. This difference is called the deficiency of the word w with respect to A and will be denoted df A (w).

For a fixed k ≥ 1, a word w ∈ Σ * is called k-compressing for A if df A (w) ≥ k. An automaton A is k-compressible if there exists a k-compressing word for A. A word w ∈ Σ * is k-collapsing (over Σ) if it is k-compressing for every k-compressible automaton with the input alphabet Σ. A word v is called k-synchronizing if it is k-compressing for all k-compressible automata with k + 1 states. Of course a k-collapsing word is also k-synchronizing.

The concept of a k-collapsing word is a natural automata-theoretic interpretation of the notion of words with the property ∆ k introduced for algebraic motivations in [START_REF] Sauer | Composing functions to reduce image size[END_REF]. Actually k-collapsing words can be seen as universal testers for checking whether an automaton is k-compressible. They are a blackbox versions of words considered in the so called generalized Černý conjecture that extends the celebrated Černý conjecture [START_REF] Černý | Poznámka k homogénnym eksperimentom s konečnými automatami[END_REF]. Recall that the former conjecture deals with the length of the shortest k-compressing word for a given k-compressible automaton. In [START_REF] Sauer | Composing functions to reduce image size[END_REF] it was proved that k-collapsing words always exist, for each Σ and each k ≥ 1, by means of a recursive construction which gives a word whose length is doubly exponential as function of k. Then better lower and upper bounds for the length c(k, t) of the shortest k-collapsing words on an alphabet of cardinality t were given in [START_REF] Margolis | Words guaranteeing minimum image[END_REF] and the lower bound for the case k = 2 was slightly improved in [START_REF] Pribavkina | On some properties of the language of 2-collapsing words[END_REF]. So far for the case k = 2 the best known bounds are the following: 2t 2 ≤ c(2, t) ≤ t 3 + 3t 2 + 2t.

In [START_REF] Ananichev | Image reducing words and subgroups of free groups[END_REF][START_REF] Ananichev | An inverse automata algorithm for recognizing 2collapsing words[END_REF], two different algorithms for deciding whether a word is 2-collapsing are given and another more combinatorial approach to the same problem is presented in [START_REF] Cherubini | A combinatorial approach to collapsing words[END_REF]. Here we get a better upper bound for c(2, t), namely c(2, t) ≤ t 3 +6t 2 +5t 2 , by means of the latter approach. Moreover we prove that this bound can be improved at least for small values of t: we build, again by using this approach, shorter 2-collapsing words on alphabets of cardinality 4 and 5. The reader is referred to [START_REF] Margolis | Words guaranteeing minimum image[END_REF] and to [START_REF] Ananichev | Collapsing words: a progress report[END_REF] for some further references and connections to some topics in Theoretical Computer Science, Language Theory and Combinatorics. Here for sake of completeness we shortly recall notation and main properties.

We view an automaton A = Q, Σ, δ as a set of transformations on Q labelled by letters of Σ rather than as a standard triple. By transformations of A we mean those transformations on Q that are induced via δ by letters of Σ. In order to define an automaton it is enough just to assign to every letter of Σ a transformation on Q. Now, for a ∈ Σ, df A (a) = 0 if and only if the corresponding transformation is a permutation on Q. If df A (a) = 1, then there is a state z ∈ Q which does not belong to the image Qa and two different states x, y ∈ Q satisfying xa = ya; in such a case the corresponding transformation will be referred to as a transformation of type {x, y}\z (x, y have the same image under the transformation, z is missed). The semigroup generated by the transformations of A consists precisely of the transformations corresponding to words in Σ * . It contains a group generated by those transformations that are permutations; this group is called the group of permutations of A.

It is well known ( [START_REF] Margolis | Words guaranteeing minimum image[END_REF]) that each 2-collapsing word over a fixed alphabet Σ is 2-full, i.e. it contains any word of length 2 on Σ among its factors, hence to characterize 2-collapsing words it is enough to consider 2-full words compressing each 2-compressible automata such that no word of length 2 is 2-compressing for them (proper 2-compressible automata, for short). Proper 2-compressible automata must have both non-permutation and permutation transformations and they are characterized by the following:

3. there are two states x, y such that each non-permutation transformation is of type {x, y}\x or {x, y}\y, both types occur, and the group of permutations does not fix the set {x, y}.

Automata of the first two types are called MONO-automata, of the latter one are called STEREOautomata.

In [START_REF] Cherubini | A combinatorial approach to collapsing words[END_REF] it is proved that a word w ∈ Σ * is 2-collapsing if and only if certain systems of conditions on permutations have only trivial solutions. We recall some notations from [START_REF] Cherubini | Synchronizing and collapsing words[END_REF]. In the sequel, as no confusion can raise, we view the set Q of the states of A as a set of natural numbers: Q = {1, 2, ..., n}, so that permutations on Q can be viewed as elements of the symmetric group Sym n . The two states x, y occurring in Proposition 1 will be then denoted by 1 and 2. By a role assignment we mean an arbitrary partition of the alphabet Σ with a distinguished nonempty block Π ⊂ Σ. Roughly speaking letters in Π play the role of permutation letters of Σ and the remaining letters play the role of non-permutation letters. Let Υ = Σ \ Π. Since non-permutation letters in proper 2-compressible automata can be of different types, a role assignment induces on Υ a further partition in non empty blocks. We denote this partition either as {D 2 , . . . , D h }, h ≥ 2, where letters in D i will play the role of the non-permutation letters of the form {1, i}\1 or as {E 1 , E 2 } where letters in E 1 , E 2 will play the role of non-permutation letters of the form {1, 2}\1 and {1, 2}\2 respectively. In the first case the partition of Σ will be called a MONO-role assignment (DB-partition in [START_REF] Cherubini | A combinatorial approach to collapsing words[END_REF]) and in the latter a STEREO-role assignment (3DB-partition in [START_REF] Cherubini | A combinatorial approach to collapsing words[END_REF]).

Let (Π, Υ) be an arbitrary role assignment, then each word w ∈ Σ + can be uniquely represented in the following form:

w = u 0 p 1 u 1 ...u m-1 p m u m (1)
where p 1 , . . . , p m ∈ Π + , u 1 , . . . , u m-1 ∈ Υ + , u 0 , u m ∈ Υ * and m is a positive integer. We say that a factor p i of the decomposition ( 1) is an inner factor if both u i-1 and u i are non-empty. Then for a MONO-role assignment (Π, Υ) for each a ∈ Υ we denote by S a the set of the inner factors p i of w such that a is the first letter in u i . Otherwise if (Π, Υ) is a STEREO-role assignment (Π, {E 1 , E 2 }) we denote by S k , k = 1, 2, the sets of the inner factors p i of w such that the last letter of u i-1 belongs to E k . We assign to the word w ∈ Σ + , for each role assignment and for each inner factor p i , a permutation condition of the form:

-1p i ∈ {1, j} if the role assignment is MONO and p i ∈ S a with a ∈ D j , -kp i ∈ {1, 2}, k = 1, 2, if the role assignment is STEREO and p i ∈ S k . Then each role assignment associates to w a system of permutation conditions formed by all the permutation conditions corresponding to the inner factors of w. In case of a MONO-role assignment (Π, Υ) such system will be denoted Γ w (Π, Υ) otherwise it will be denoted Γ ′ w (Π, Υ). Since letters of Π are regarded as permutations acting on a finite set of positive integers {1, 2, . . . , n} (representing Q), conditions of the form jv ∈ A with j positive integer, v ∈ Π + , A ⊆ {1, 2, . . . , n} mean that the image of j under the product v of permutations belongs to the set A. We say that a system of permutation conditions has a solution if there exists an assignment of permutations on a finite set {1, 2, . . . , n} to letters in Π such that all the conditions in the system are satisfied. Obviously the systems associated to w by each role assignment have always the solution where all permutations are the identity. A solution of the system Γ w (Π, Υ), associated to w by a MONO-role assignment, is called trivial if all permutations fix 1. Also, in the special case when Υ consists of the unique block D 2 (and as a consequence, all j's on the right hand side of the conditions are equal to 2), a solution with all permutations fixing the set {1, 2} is considered trivial. The remaining solutions are nontrivial. Similarly a solution of the system Γ ′ w (Π, Υ), associated to w by a STEREO-role assignment (Π, Υ) is called trivial if all the permutations fix {1, 2}.

In [START_REF] Cherubini | A combinatorial approach to collapsing words[END_REF] 2-collapsing words were characterized in terms of permutation conditions in the following way.

Theorem 2 ([8]

) A word w ∈ Σ + is 2-collapsing if and only if it is 2-full and the following conditions hold:

1. For each MONO-role assignment (Π, Υ) of Σ all the solutions of the system Γ w (Π, Υ) are trivial.

2. For each STEREO-role assignment (Π, Υ) of Σ all the solutions of the system Γ ′ w (Π, Υ) are trivial.

By the above Theorem 2 one can readily derive the following characterization of 2-synchronizing words.

Corollary 3 A word w ∈ Σ + is 2-synchronizing if and only if it is 2-full and for each role assignment (Π, Υ) of Σ all the solutions of the systems Γ w (Π, Υ) (in case of MONO-role assignments) and Γ ′ w (Π, Υ) (in case of STEREO-role assignments) in the semigroup T 3 of all transformations on 3 letters are trivial.

Main result.

We introduce some useful notations. Definition 1 . A permutation p on {1, 2, ..., n} is special with respect to the ordered pair (i, j), i, j ∈ {1, 2, ..., n}, whether it fixes either {i} or {i, j}. Two permutations p, z are special of the same type with respect to the ordered pair (i, j) if both p and z fix {i} or both of them fix {i, j}.

In the sequel by (i)..., (ij)..., (ijh...)... we will denote respectively a permutation fixing i, containing a cycle (i, j), containing a cycle (ijh...) of arbitrary length.

Note that the property of being special of the same type with respect to (i, j) is not transitive; e.g. both the permutations p = (1)(2...n) and z = (12)(3...n) are special of the same type as y = (1)(2)(3...n) with respect to (1, 2), but they are not of the same type. Note however that two special permutations p and z can be of the same type of y with respect to (i, j) without being of the same type only if one of them fixes {i} and does not fix j, the other has a cycle (ij) while y fixes both {i} and {j}. Trivial solutions of systems introduced before Theorem 2 are special of the same type with respect to (1, 2), so we are interested in sets of equations whose occurrence in a system guarantees that solutions are special of the same type with respect to (1, 2). Lemma 4 Let p, z be two permutations on {1, 2, ..., n} and let i, j ∈ {1, 2, ..., n}. The permutations p, z fulfil the conditions:

1. ip ∈ {i, j} 2. ip 2 ∈ {i, j} 3. iz ∈ {i, j} 4. iz 2 ∈ {i, j} 5. ipzp ∈ {i, j} (or izpz ∈ {i, j})
if and only if they are special of the same type with respect to (i, j).

Proof:

The "if part" is trivial. Conversely from condition 1. we immediately get that either p fixes i or it is of the form p = (ij...)... and condition 2. gives that in such case p = (ij).... Similarly conditions 3. and 4. give that z either fixes i or has the form z = (ij).... Now if z = (ij)... and p fixes i then p fixes also j otherwise condition 5. is not fulfilled. If p = (ij)... then jz = ipz ∈ {i, j} by condition 5. whence z fixes {i, j}. ✷

Similarly, the following can be proved:

Lemma 5 Let p, z be two permutations on {1, 2, ..., n} and let i, j ∈ {1, 2, ..., n}. The permutations p, z fulfil the conditions:

1. ip ∈ {i, j} 2. ip 2 ∈ {i, j} 3. iz 2 ∈ {i, j} 4. ipz ∈ {i, j} 5. izp ∈ {i, j}
if and only if they are special of the same type with respect to (i, j).

Theorem 6

The minimal 2-collapsing word on t letters has length less than or equal to

t 3 + 6t 2 + 5t 2 .
Proof: To show our bound we want to exhibit a 2-collapsing word, similar to the one introduced in [START_REF] Margolis | Words guaranteeing minimum image[END_REF]. Consider an alphabet Σ = {a 1 , a 2 , ..., a t } on t letters in the lexicographic order and let u = a 1 a 2 ...a t and

w = u( q∈X qu)
where X = {x, x 2 , xyx : x, y ∈ Σ , y > x}.

We want to prove that the word w is 2-collapsing. Let us consider different role assignments (Π, Υ) of Σ.

Assume that (Π, Υ) is a STEREO-role assignment with Υ = {E 1 , E 2 }; let h, k be respectively the least and the greatest index of an element in Υ and let a j be an element in Υ belonging to a different block than a k (eventually h = j). Each a i , i > k (if any) fixes {1, 2}, since the factors a k a i a k , a j a i a j occur in w whence both the equations 1a i ∈ {1, 2} and 2a i ∈ {1, 2} occur in Γ ′ w (Π, Υ). More the product a 1 a 2 ...a h-1 fixes {1, 2}. In fact a j (a 1 a 2 ...a h-1 )a h and a k (a 1 a 2 ...a h-1 )a h are factors of w and all a 1 , ..., a h-1 are in Π hence both the equations 1(a 1 a 2 ...a h-1 ) ∈ {1, 2} and 2(a 1 a 2 ...a h-1 ) ∈ {1, 2} occur in Γ ′ w (Π, Υ). This yields that also any a i , i < h (if any) fixes {1, 2}, since also a i a j a i (a 1 a 2 ...a h-1 )a h and a i a k a i (a 1 a 2 ...a h-1 )a h are factors of w whence both the equations 1a i (a 1 a 2 ...a h-1 ) ∈ {1, 2} and 2a i (a 1 a 2 ...a h-1 ) ∈ {1, 2} occur in Γ ′ w (Π, Υ) with a 1 a 2 ...a h-1 fixing {1, 2}. Similarly, at last, each

a i : h < i < k (if any) fixes {1, 2}.
In fact either a h and a k are in different blocks or there is an a j ∈ Υ belonging to a different block with respect to a h and a k , so for each i, h < i < k there are two indices s, r, h ≤ s < i < r ≤ k such that a s and a r are in different blocks of Υ, hence a i a r a i (a 1 a 2 ...a h-1 )a h and a s a i a s are factors of w.

Then let (Π, Υ) be a MONO-role assignment with Υ = {D 2 , D 3 , ...D g } with g > 2.

Let k be the greatest index such that a k ∈ Υ then a k ∈ D k ′ for some k ′ . Let D j ′ be a block of Υ different from D k ′ and let a j ∈ D j ′ . We will prove that every a i ∈ Π fixes {1}. In fact if i > k then a k a i a k , a j a i a j are factors of w hence both the equations 1a i ∈ {1, k ′ }, 1a i ∈ {1, j ′ } occur in the system Γ w (Π, Υ), whence a i fixes {1} for all a i ∈ Π with i > k, if any. Now let i < k. If j < i < k then a j a i a j , a k a k+1 ...a t a i a k a i are factors of w, if i < j then a k a k+1 ...a t a i a j a i , a k a k+1 ...a t a i a k a i are factors of w and all elements a k+1 , ..., a t are in Π, hence they fix {1}. Then in the system Γ w (Π, Υ) there are either the equations 1a i ∈ {1, j ′ } and 1a k+1 ...a t a i ∈ {1, k ′ } or 1a k+1 ...a t a i ∈ {1, j ′ } and 1a k+1 ...a t a i ∈ {1, k ′ } from which in both cases we get that 1a i ∈ {1, k ′ } and 1a i ∈ {1, j ′ }, thus all a i ∈ Π fix {1}.

At last suppose that Υ consists of only one block, i.e. g = 2, and let h, k respectively be the least and the greatest index of an element in Υ. Denote v 1 = a 1 ...a h-1 and v 2 = a k+1 ...a t , then a h v 1 a h , a k v 2 a k are factors of w whence 1v 1 , 1v 2 ∈ {1, 2} are equations occurring in Γ w (Π, Υ).

In this case, suppose first that 1v 2 = 1. Since for all a i ∈ Σ, a k v 2 a i v 1 a h and a k v 2 a 2 i v 1 a h are factors of w, equations in Γ w (Π, Υ) give 1a i v 1 ∈ {1, 2} and 1a 2 i v 1 ∈ {1, 2}. Moreover since w contains a k a i a k or a k v 2 a i a k a i we have 1a i ∈ {1, 2} for every a i ∈ Σ. If all the letters a i fix 1, then we are done. Otherwise suppose there is a letter a i such that 1a i = 2. Then we get 2v 1 ∈ {1, 2} and since 1v 1 ∈ {1, 2} we obtain that v 1 fixes {1, 2}. Thus from 1a i 2 v 1 ∈ {1, 2} we get 2a i = 1 and a i = (12).... To prove that in this case all permutations are of the same type, note that whenever a factor a k v 2 a i a j a i v 1 a h appears in w we have 1a i a j a i ∈ {1, 2} and then apply Lemma 4.

Suppose now 1v 2 = 2. Then 2a i v 1 , 2a 2 i v 1 ∈ {1, 2} for every a i ∈ Π. Let us prove that v 1 must fix {1, 2}. This is trivial if h = 1 and v 1 is empty, else let {1, 2} = {1v 1 , zv 1 } for some z and prove that z = 2. For all i : 1 ≤ i < h a k v 2 a i a h a i and a i a h a i v 1 a h are factors of w, hence 1v 2 a i ∈ {1, 2} and 1a i v 1 ∈ {1, 2} are equations in Γ w (Π, Υ), so that 2a i ∈ {1, 2} and a i v 1 fixes {1, 2}. If for some i : 1 ≤ i < h: 2a i = 2a 2 i then a i = (2)... and 2v 1 ∈ {1, 2} whence z = 2; else {2a i , 2a 2 i } = {1, z} which immediately yields a i = (2 1 z...)... since 2 = 2a i ∈ {1, 2}. If there exist two such elements a i , a j , 1 ≤ i < j < h then the factor a k v 2 a i a j a i v 1 a h occurs in w so that 1v 2 a i a j a i v 1 = (2a i a j )a i v 1 ∈ {1, 2} is an equation in Γ w (Π, Υ) whence 2a i a j = z ∈ {1, 2} and z = 2; but if only one element a i of this type exists then z = 1a i = 1v 1 ∈ {1, 2}. Thus v 1 fixes {1, 2}, which immediately yields 2a i , 1a i ∈ {1, 2} for every a i ∈ Π, i < k by the occurrence of the factor a k v 2 a i a k a i v 1 a h , and for every a i ∈ Π, i > k by the occurrence of the factors a k a i a k and a k v 2 a i v 1 a h ; hence all elements in Π fix {1, 2} so that they are special of the same type.

Thus w is 2-collapsing because the systems associated to w for each role assignment (Π, Υ) have only trivial solutions and the length of the word w is:

t + t(t + 1) + t(t + 2) + t(t -1) 2 (t + 3) = t 3 + 6t 2 + 5t 2 .
✷ 3 Short 2-collapsing words.

The bound found in Theorem 6 is lower than the one given in [START_REF] Margolis | Words guaranteeing minimum image[END_REF], but still for small values of n it reveals to be not efficient: indeed for n = 3, 4, 5 it respectively gives |w| ≤ 48, 90, 150. It was proved in [START_REF] Ananichev | Quest for short synchronizing words and short collapsing words[END_REF] that the shortest 2-collapsing words on 3 letters have length 21 and the shortest 2-synchronizing words on 3 letters have length 20, while a 2-collapsing word on 4 letters is known whose length equals 58 ([4]). But we can use our lemmas to get shorter 2-collapsing and 2-synchronizing words on 4 and 5 letters.

We will make a systematic use of the following Lemma 7 Let w be a word on an alphabet Σ with |Σ| ≥ 2, let Σ ′ ⊆ Σ and w ′ ∈ Σ ′+ be a factor of w, which is a 2-collapsing word on Σ ′ . For a role assignment

(Π, Υ) of Σ let Π ′ = Π ∩ Σ ′ and Υ ′ = Υ ∩ Σ ′ and for each block E i (D i ) in Υ let E ′ i = E i ∩ Σ ′ (D ′ i = D i ∩ Σ ′ ).
Then for each role assignment (Π, Υ) such that ∅ = Π ′ and ∅ = Υ ′ the following properties hold: w (Π, Υ) all the elements in Π ′ fix the set {1, 2}. In all the above cases, if Π ′ = Π then the system associated to w for (Π, Υ) has only trivial solutions.

• If (Π, Υ) is a MONO-role assignment with Υ = D 2 ,
Proof: If (Π, Υ) is a MONO-role assignment, then (Π ′ , Υ ′ ) is a MONO-role assignment of Σ ′ and the equations of Γ w ′ (Π ′ , Υ ′ ) occur in Γ w (Π, Υ)
, hence all solutions of the latter system are also solutions of the former. Hence if Υ and consequently Υ ′ has only one block, then all elements in Π ′ are special permutations relative to (1, 2) which all fix {1} or all fix {1, 2}, because w ′ is 2-collapsing. Similarly if Υ ′ is formed by at least two blocks then all elements in Π ′ fix {1}. If (Π, Υ) is a STEREO-role assignment of Σ, and Υ ′ has two non trivial blocks, then (Π ′ , Υ ′ ) is a STEREO-role assignment of Σ ′ hence the equations of Γ ′ w ′ (Π ′ , Υ ′ ) occur in Γ ′ w (Π, Υ) and so all elements in Π ′ are special permutations relative to (1, 2) which all fix {1, 2}. The last statement is trivial. ✷

It is important to remark, using the same notation and the same arguments of the above Lemma 7, that if (Π, Υ) is a MONO-role assignment with more than one block different from Π, while Υ ′ is formed by a unique block D ′ i , then in each solution of Γ w (Π, Υ) all the elements in Π ′ are special of the same type with respect to {1, i}. Similarly if (Π, Υ) is a STEREO-role assignment of Σ and E ′ 1 = ∅ then in each solution of Γ ′ w (Π, Υ) all the elements in Π ′ are special of the same type with respect to (2, 1) while if E ′ 2 = ∅ then all the elements in Π ′ are special of the same type with respect to (1, 2). Proposition 8 c(2, 4) ≤ 56

Proof: Let Σ = {a, b, c, d} and let

r = cabac 2 bacbcacb 2 a 2 c, s = dadbda 2 b 2 dabd 2 ab, u = adacdbcadac 2 d 2 cbdca.
Consider the word w = r(bab)su. Of course |w| = 56; we want to prove that w is 2-collapsing. In order to exhibit w we made use of two of the minimal 2-collapsing words on 3 letters. Namely u 1 = r(bab) is the 55-th word in the list in [START_REF] Ananichev | Quest for short synchronizing words and short collapsing words[END_REF] on the alphabet {c, a, b}, while u 2 = (bab)s(ad) is the 11-th one in that list on the alphabet {b, a, d}. Both the words u 1 and u 2 are 2-collapsing, as shown in [START_REF] Ananichev | Quest for short synchronizing words and short collapsing words[END_REF]. Put Σ 1 = {a, b, c} and Σ 2 = {a, b, d}.

Let us consider different role assignments (Π, Υ) of Σ and put

Π i = Π ∩ Σ i , Υ i = Υ ∩ Σ i , for i = 1, 2.
Let |Π| = 1 and Π ⊂ {a, b} then Π 1 = Π 2 = Π. Moreover if (Π, Υ) induces on Υ a partition in more than one block then there is at least an i = 1, 2 such that Υ i contains two non empty blocks, so the system associated to w for (P, Υ) has only trivial solutions by Lemma 7. Then let Π = {c}. If (Π, Υ) is a MONO-role assignment and Υ consists of only one block, then all the solutions of Γ w (Π, Υ) are trivial by Lemma 7. If Υ consists of more than one block then one has to consider the factors acb, bca of w if the letters a and b belong to different blocks, else consider the factors acd and dca. In both cases, if (Π, Υ) is a MONO-role assignment then the equations 1c ∈ {1, 2}, 1c ∈ {1, 3} occur in Γ w (Π, Υ) hence c fixes {1}. If (Π, Υ) is a STEREO-role assignment then the equations 1c ∈ {1, 2}, 2c ∈ {1, 2} occur in Γ ′ w (Π, Υ), hence c fixes the set {1, 2}. The same argument applies when Π = {d}, considering the factors adb, bda or bdc, cdb.

Let |Π| = 2. Assume Υ = {a, b}. Then for all i = 1, 2, ∅ = Π i = Π and Υ = Υ i . Then if Υ is formed by two blocks then all the solutions of the system associated to w for (Π, Υ) are trivial: by Lemma 7 if (Π, Υ) is a MONO-role assignment then both c, d fix {1}, if (Π, Υ) is a STEREO-role assignment then both c, d fix {1, 2}. Otherwise if Υ is formed by a unique block we only get that c and d are special permutations relative to [START_REF] Ananichev | Image reducing words and subgroups of free groups[END_REF][START_REF] Ananichev | An inverse automata algorithm for recognizing 2collapsing words[END_REF]. But since w contains the factors acdb, bdca, the equations 1cd ∈ {1, 2}, 1dc ∈ {1, 2} occur in Γ w (Π, {a, b}) hence c, d are special permutations of the same type with respect to (1, 2), i.e. the system Γ w (Π, {a, b}) has only trivial solutions. Then let Υ = {a, b}, whence Π = Π i for some i = 1, 2. Hence if Υ is formed by a unique block then Γ w (Π, Υ) has only trivial solutions by Lemma 7. Otherwise we only get that the solutions of the systems associated to w for (Π, Υ) are either special permutations relative to (1, 2) or fix {2}. Denote by β 1 , β 2 the elements in Π and by α 1 , α 2 the elements in Υ; for every choice of (Π, Υ) where Υ = {a, b} is formed by two blocks, there is an i = 1, 2 such that α h β i α h and either α h β ǫ i β 3-i α h or α h β ǫ i β 3-i α 3-h (where ǫ ∈ {0, 1} and β 0 i is the empty word) are factors of w for all h = 1, 2. Then if (Π, Υ) is a STEREO-role assignment then the equations

1β i ∈ {1, 2}, 2β i ∈ {1, 2}, 1β ǫ i β 3-i ∈ {1, 2}, 2β ǫ i β 3-i ∈ {1, 2} occur in Γ ′ w (Π, Υ)
, and this yields that the solutions of the systems are pairs of special permutations which both fix the set {1, 2}, i.e. the system has only trivial solutions. Otherwise if (Π, Υ) is a MONO-role assignment with three blocks the equations

1β i ∈ {1, 2}, 1β i ∈ {1, 3}, 1β ǫ i β 3-i ∈ {1, 2}, 1β ǫ i β 3-i ∈ {1, 3} occur in Γ w (Π, Υ)
, and this yields that the solutions of the systems are pair of trivial permutations which both fix {1}, hence again the system has only trivial solutions.

Let |Π| = 3. If Υ = {α} ⊂ {a, b} then for all i = 1, 2 Υ i = Υ, hence the solutions of Γ w (Π, Υ) are triples of special permutations of the same type of γ ∈ {a, b} -Υ, since they are also solutions of Γ ui (Π i , Υ i ). If these permutations are not all of the same type then it must be γ = (1)(2).... Then if γ = b consider the factor acdbca of w, otherwise consider the factor badacdb of w. In the first case the equation 1cdbc ∈ {1, 2} occurs in Γ w (Π, Υ), in the second case 1adacd ∈ {1, 2} occurs in Γ w (Π, Υ), and both the equations together with γ = (1)(2)... yield that c, d are of the same type. Hence the system Γ w (Π, Υ) has only trivial solutions.

If Υ = {c} then a, b are special permutations of the same type with respect to (1, 2) since they are solutions of Γ u1 ({a, b}, {c}), whence 1a, 1a Like in the proof of Proposition 8 the word w 1 is 2-collapsing on the letters {a, b, c, d} and symmetrically the word w 2 is 2-collapsing on the letters {a, b, c, e}: we only changed the order of some parts, but still we involved as factors some of the minimal 2-collapsing words on three letters. The factors in u and u ′ (ca) strictly correspond to the one we considered in the proof of Proposition 8.

More, let v = cedbeacdebdedbedade 2 d 2 ecedce and finally w = s ′ u ′ r(bab)suv. (Note that w contains all the factors of w 2 ). Of course |w| = 119; we want to prove that w is 2-collapsing. Let us consider different role assignments (Π, Υ) of Σ and put Π i = Π ∩ Σ i , Υ i = Υ ∩ Σ i , for i = 1, 2.

If |Π| = 1 arguments like the ones applied in the proof of Proposition 8 can be used to prove that the system associated to w for (Π, Υ) has only trivial solutions.

Let |Π| = 2, 3. Assume that, for some i = 1, 2, Π ⊆ Σ i . If Υ is formed by a unique block, then the system associated to w for (Π, Υ) has only trivial solutions by Lemma 7; the same happens when both Υ i and Υ are decomposed in more than one block. So, for all i such that Π ⊆ Σ i , Υ i is formed by a unique block while Υ is formed by more than one block. It is easy to check that if Π ⊂ {a, b, c} then either Υ 1 or Υ 2 are formed by two blocks. Then assume Π = {a, b, c}, whence Υ = ({d}, {e}). Hence all the solutions of the system associated to w for (Π, Υ) fix {1, 2} by the remark after Lemma 7. Assume that Π is not a subset of {a, b, c} and Π ⊆ Σ 1 , then Π 1 = Π and Υ 2 = Υ = (Υ 1 , {e}). In all the solutions of the system associated to w for (Π, Υ) by Lemma 7 the elements in Π 2 fix {1, 2} if (Π, Υ) is a STEREO-role assignment and fix {1} if it is a MONO-role assignment. Moreover each solution of the system associated with w for (Π, Υ) is formed by permutations which either fix {1, 2} or fix {1} or fix {2} (by remark after

  , 1cb ∈ {1, 2} whence again b and c are trivial solutions of the same type by Lemma 5. Finally, let a = (12)...; then b fixes {1, 2} whence 2c, 1c ∈ {1, 2}. ✷ Proposition 9 c(2, 5) ≤ 119 Proof: Let Σ = {a, b, c, d, e} and let r = cabac 2 bacbcacb 2 a 2 c, s = dadbda 2 b 2 dabd 2 ab, u = adacdbcadac 2 d 2 cbdca, s ′ = abeaebea 2 b 2 eabe 2 ab, u ′ = aeacebcaeac 2 e 2 cbe. Consider the words w 1 = r(bab)su ∈ {a, b, c, d} + and w 2 = bs ′ u ′ r(bab) ∈ {a, b, c, e} + .

  then in each solution of Γ w (Π, Υ) the elements in Π ′ are special of the same type with respect to[START_REF] Ananichev | Image reducing words and subgroups of free groups[END_REF][START_REF] Ananichev | An inverse automata algorithm for recognizing 2collapsing words[END_REF]). MONO-role assignment with Υ = {D 2 , D 3 , ...D g }, g > 2, and there are at least two non empty blocks D ′ i1 , D ′ i2 , then in each solution of Γ w (Π, Υ) all the elements in Π ′ fix {1}. • If (Π, Υ) is a STEREO-role assignment and both E ′ 1 , E ′ 2 are nonempty, then in each solution of Γ ′

• If (Π, Υ) is a a

  2 , 1b, 1b 2 ∈ {1, 2} and b, d are special solutions of the same type with respect to (1, 2) by applying Lemma 5 to Γ u ({a, b}, {c}) ∪ {1b, 1b 2 ∈ {1, 2}}. Whence 1d, 1d 2 ∈ {1, 2} and again a, d are special solutions of the same type with respect to (1, 2) by applying Lemma 4 to Γ u ({a, b}, {c}) ∪ {1a, 1a 2 , 1d, 1d 2 ∈ {1, 2}}. If Υ = {d}, then a, b are special solutions of the same type with respect to (1, 2) since they are solutions of Γ u2 ({a, b}, {d}), whence 1a, 1a 2 , 1b, 1b 2 ∈ {1, 2}. More 1ac, 1bca, 1ac 2 , 1cb ∈ {1, 2} by Γ u ({a, b}, {d}). If a fixes {1} but does not fix {2}, then b too fixes {1} and we immediately get 1ac, 1ca, 1c 2 , 1c ∈ {1, 2} whence a and c are special solutions of the same type with respect to (1, 2) by applying Lemma 5 so that also c fixes {1}. If a = (1)(2)... then 1c, 1bc, 1c

  2

Acknowledgements

The authors thank Elena Pribavkina for informing them about the results of applying her algorithm on the short 2-collapsing words presented in [7] and for her careful reading of the present paper.

† This research was partially supported by the ESF programme Automatha 1365-8050 c 2009 Discrete Mathematics and

 Lemma 7). So let (Π, Υ) be a STEREO-role assignment. Then the solutions of the system Γ ′ w (Π, Υ) either fix all {1, 2}, or all fix {1} ({2}) and the elements in Π 2 are of the form (1)(2).... In the latter case, since edbe, edce are factors of w, when either b or c are in Π 2 we get that d too has the form (1)(2)..., otherwise we get again that d has the form (1)(2)... because w has the factors edb, edc. Hence Γ ′ w (Π, Υ) has only trivial solutions. Then let (Π, Υ) be a MONO-role assignment (with more than one block in Υ). Since w contains all the factors ade, bde, cde we get that d fixes {1}, whence Γ w (Π, Υ) has only trivial solutions. Similar arguments apply when Π is not a subset of {a, b, c} and Π ⊆ Σ 2 . So let {d, e} ⊆ Π. Obviously Υ i = Υ for all i = 1, 2. Then if Υ contains at least two blocks then the solutions of the system associated to w for (Π, Υ) are trivial by Lemma 7. So let (Π, Υ) be a MONO-role assignment with a unique block in Υ. Then all the solutions of Γ w (Π, Υ) are formed by special permutations with respect to (1, 2) and if |Π i | > 1 then the permutations in Π i are of the same type. Assume that the permutations in Π 1 and in Π 2 are not of the same type then if Π ⊆ {a, d, e}, the factors cdeb, bdec, cedb, bedc give that both d, e fix {1, 2}. Moreover beaeb is a factor of w so again both a, e fix {1, 2} provided that a ∈ Π. Now let Π = {b, d, e}. If there is a solution of Γ w (Π, Υ) which is not trivial then b has the form (1)(2)..., and the factor cedbea gives that both d, e fix {1, 2}. If Π = {c, d, e} then if there is a solution of Γ w (Π, Υ) which is not trivial then c has the form (1)(2)..., and again the factor bdedb gives that both d and e fix {1, 2}. In Proposition 8 of [START_REF] Cherubini | A bound for the length of shortest 2-collapsing words[END_REF] we considered a slightly longer word, so proving that c(2, 5) ≤ 120. But in [START_REF] Pribavkina | 2-collapsing words and a sequence reconstruction problem[END_REF] an algorithm is presented to find shorter 2-collapsing words from a given 2-collapsing word. The author run her algorithm on our word and got four 2-collapsing words of length 119, one of which is the word considered in the above Proposition 9. She also did the same on the word in our Proposition 8: she could not find shorter 2-collapsing words, but found three more 2-collapsing words of the same length.

Of course Propositions 8 and 9 give upper bounds to the length of the minimal 2-synchronizing words respectively on 4 and 5 letters. But this bounds can be further improved: denote by s(2, t) the length of the least 2-synchronizing word on t letters. The word w = (cd 2 cbcd)r(ab)s(cdadc 2 d) is 2-synchronizing and |w| = 52. In order to exhibit w we used two of the minimal 2-synchronizing words on 3 letters listed in [START_REF] Ananichev | Quest for short synchronizing words and short collapsing words[END_REF]. Namely u 1 = r(ab) is the 11-th word in the list in [START_REF] Ananichev | Quest for short synchronizing words and short collapsing words[END_REF], on the alphabet Σ 1 = {c, a, b}, while u 2 = (ab)s is the 15-st one in that list, on the alphabet Σ 2 = {a, b, d}. Both the words u 1 and u 2 are 2-collapsing ( [START_REF] Ananichev | Quest for short synchronizing words and short collapsing words[END_REF]).

Let us consider different role assignments (Π, Υ) of Σ and put

The cases when |Π| = 1, 2 can be proved with similar arguments as in the proof of Proposition 8.

Let |Π| = 3. We are looking for solutions of our systems of equations on 3 permutations t, y, z in the symmetric group Sym 3 . If a system has only special solutions with respect to {1, 2} and t, y are of different types while both of them are of the same of z, then without loss of generality t = ( 12 The word w 1 (resp. w 2 ) is 2-synchronizing on the alphabet {a, b, c, d} (resp. {a, b, d, e}), by similar arguments as in the proof of Proposition 10. In fact it is built from two words in the list in [START_REF] Ananichev | Quest for short synchronizing words and short collapsing words[END_REF] for suitable alphabets: r(ab) is the 6-th and (ab)s is the 16-th (resp. (ab)s ′ is the 16-th while (dad)r ′ is the 1-st) and u (resp. u ′ ) gives us the other necessary factors.

The word w = vur(ab)sr ′ u ′ v ′ is 2-synchronizing and its length equals 111. ✷


Yidong Sun

Zhiping Wang

String Pattern Avoidance in Generalized Non-crossing Trees

Keywords: Generalized non-crossing tree, pattern avoidance, Catalan number, little Schröder path

The problem of string pattern avoidance in generalized non-crossing trees is studied. The generating functions for generalized non-crossing trees avoiding string patterns of length one and two are obtained. The Lagrange inversion formula is used to obtain the explicit formulas for some special cases. A bijection is also established between generalized non-crossing trees with special string pattern avoidance and little Schröder paths.

Introduction

A non-crossing tree (NC-tree for short) is a tree drawn on n vertices in {1, 2, • • • , n} arranged in counterclockwise order along a circle such that the edges lie entirely within the circle and do not cross. Noncrossing trees have been investigated by Chen and Yan [START_REF] Chen | Noncrossing trees and noncrossing graphs[END_REF], Deutsch and Noy [START_REF] Deutsch | Statistics on non-crossing trees[END_REF], Flajolet and Noy [START_REF] Flajolet | Analytic combinatorics of non-crossing configurations[END_REF], Gu, et al. [START_REF] Gu | 2-binary trees: bijections and related issues[END_REF], Hough [START_REF] Hough | Descents in noncrossing trees[END_REF], Noy [START_REF] Noy | Enumeration of noncrossing trees on a circle[END_REF], Panholzer and Prodinger [START_REF] Panholzer | Bijections for ternary trees and non-crossing trees[END_REF]. Recently, some problems of pattern avoidance in NC-trees have been studied by Sun and Wang [START_REF] Sun | Pattern avoiding in non-crossing trees[END_REF]. It is well known that the set of NC-trees with n + 1 vertices is counted by the generalized Catalan number 1 2n+1 3n n [12, A001764]. A generalized non-crossing tree (GNC-tree for short) is a generalization of ordinary non-crossing tree such that the vertices along the circle are not necessarily labelled by 1, 2, . . . , n, but only weakly increasing, beginning with 1 and without "gaps". See Figure 2 for an example.

In the sequel, we are concerned with rooted GNC-trees where the first 1 is the root. Let GNC n denote the set of rooted GNC-trees of n + 1 vertices. It is easy to prove that GNC n is counted by |GNC n | = 2 n 2n+1 3n n [12, A153231]. A descent (an ascent, a level) is an edge (i, j) such that i > j (i < j, i = j) and i is on the path from the root to the vertex j. If encoding an ascent by u, a level by h and a descent by d, then each path in a GNC-tree can be represented by a ternary word on {u, h, d} by reading the path from the root. In analogy with the well-established permutation patterns [START_REF] Simion | Restricted permutations[END_REF][START_REF] Wilf | The patterns of permutations[END_REF], we propose a definition of patterns in GNC-trees. However, it should be pointed out that in the present paper we are dealing with "string pattern avoidance" (only consecutive letters are considered), which is thus different from "pattern avoiding" as defined in [START_REF] Simion | Restricted permutations[END_REF][START_REF] Wilf | The patterns of permutations[END_REF]. Definition 1.1 Let w = w 1 w 2 . . . w n and σ = σ 1 σ 2 . . . σ k be two ternary words on {u, h, d}. Then w contains the string pattern σ if it has a subword w i+1 w i+2 . . . w i+k equal to σ for some 0 ≤ i ≤ nk; otherwise w is called σ-avoiding. A GNC-tree T is called σ-avoiding if T has no subpath (viewed from the root) encoded by σ.

Let P k denote the set of ternary words of length k on {u, h, d}. For any σ ∈ P k , let GNC m n (σ) denote the set of GNC-trees in GNC n which contain the pattern σ exactly m times. For any nonempty subset P ⊂ P k , GNC n (P ) denotes the set of GNC-trees in GNC n which avoid all the patterns in P . A counterpart for GNC-trees to the analogous question for restricted permutations is the following question: Question 1.2 Determine the cardinalities of GNC n (P ) for P ⊂ P k and GNC m n (σ) for σ ∈ P k . In the literature, two kinds of special NC-trees have been considered, namely non-crossing increasing trees and non-crossing alternating trees. Both of them are counted by the Catalan numbers

C n = 1 n+1
2n n [12, A000108]. A non-crossing increasing (alternating) tree is an NC-tree with the vertices on the path from the root 1 to any other vertex appearing in increasing (alternating) order. By our notation, a non-crossing increasing tree is a d-avoiding NC-tree and a non-crossing alternating tree is a {uu, dd}avoiding NC-tree. Bijections between non-crossing alternating trees and Dyck paths have been presented in [START_REF] Stanley | Enumerative Combinatorics[END_REF]. But for GNC-trees, it seems to be shed little light on this subject.

The contents of the paper (and also the methods used) are much closer to studies of "peaks, valleys, etc." in Motzkin paths or Dyck paths [START_REF] Sapounakis | Counting strings in Dyck paths[END_REF][START_REF] Sapounakis | Counting peaks and valleys in k-colored Motzkin paths[END_REF]. In this paper, we deal with several patterns and find the corresponding generating functions for GNC-trees. More precisely, we investigate the patterns in P 1 in Section 2 and the patterns in P 2 in Section 3. The Lagrange inversion formula is used to obtain explicit formulas for some special cases. A bijection is also established between GNC-trees with special pattern avoidance and little Schröder paths.

The patterns in P 1

For any T ∈ GNC n , let u(T ), h(T ), d(T ) denote the number of ascents, levels and descents of T respectively, then u(T ) + h(T ) + d(T ) = n. Let GNC * n be the set of GNC-trees T in GNC n such that T has only one vertex with label 1, that is, only the root has the label 1 and all other vertices have labels greater than 1. Define

T x,y,z (t) = n≥0 t n T ∈GNCn x u(T ) y h(T ) z d(T ) , T * x,y,z (t) = n≥0 t n T ∈GNC * n x u(T ) y h(T ) z d(T ) .
Close relations between T x,y,z (t) and T * x,y,z (t) can be established using the "butterfly" decomposition (introduced by Flajolet and Noy [START_REF] Flajolet | Analytic combinatorics of non-crossing configurations[END_REF]) of GNC-trees in Figure 1. It is obvious that the decomposition is only used for n ≥ 1 and that the case n = 0 leads to the additional 1. Find the first and minimal label i, denoted by i , of T ∈ GNC n in counterclockwise order such that the root 1 and i form an edge, then T can be partitioned into three parts. where not all vertices are labeled by 1. The edge (1, 1) contributes a weight of yt, Part I contributes T 0,y,0 (t) and Part II contributes T x,y,z (t) -T 0,y,0 (t). For Part III, except for the one point case, by decreasing all the labels (excluding the root) by j -2 units (if k = j) or j -1 units (if k = j + 1), one can obtain two GNC-trees in GNC * n for some n ≥ 1. Part III contributes 2T * x,y,z (t) -1.

Case(iii): i ≥ 2, j ≥ i and k = j or j + 1. The edge (1, i ) contributes a weight of xt. Note that the ascents and descents are exchanged in Part I, and the labels are lying in {1, 2, . . . , i} or {2, 3, . . . , i}, so Part I contributes 2T z,y,x (t) -T 0,y,0 (t) for i ≥ 2. Part II still forms a GNC-tree after reducing the labels {i, . . . , j} to

{1, • • • , j -i + 1}, so Part II contributes T x,y,z (t). Similar to (ii), Part III contributes 2T * x,y,z (t) -1.
In summary, we have

T x,y,z (t) = 1 + ytT 0,y,0 (t) 2 T x,y,z (t)
+ ytT 0,y,0 (t) T x,y,z (t) -T 0,y,0 (t) 2T * x,y,z (t) -1 (2.1)

+ xtT x,y,z (t) 2T z,y,x (t) -T 0,y,0 (t) 2T * x,y,z (t) -1 .
For any T ∈ GNC * n , by a similar decomposition, one can derive that

T * x,y,z (t) = 1 + xtT x,y,z (t)T z,y,x (t) 2T * x,y,z (t) -1 . (2.2)
Now we solve (2.2) for T * x,y,z (t) and substitute into (2.1) to obtain

T x,y,z (t) = 1 -ytT 0,y,0 (t) 2 -xtT x,y,z (t)T 0,y,0 (t) + ytT 0,y,0 (t) 1 + T 0,y,0 (t) T x,y,z (t) + 2xt 1 -ytT 0,y,0 (t) 2 T x,y,z (t) 2 T z,y,x (t). (2.3) If x = z = 0, then (2.3) reduces to T 0,y,0 (t) = 1 + ytT 0,y,0 (t) 3 . (2.4)
Multiplying on both sides of (2.3) by T 0,y,0 (t) and using (2.4), after some routine computations, one can deduce that T x,y,z (t) = 1 + (yx)tT 0,y,0 (t) 2 T x,y,z (t) + 2xtT x,y,z (t) 2 T z,y,x (t).

(2.5)

The evaluation

x = y = z = 1 immediately gives T 1,1,1 (t) = 1 + 2tT 1,1,1 (t) 3 , which thus proves that |GNC n | = 2 n 2n+1 3n
n via generating functions. By solving (2.5) for T x,y,z (t), we have

T x,y,z (t) = 1 -(y -x)tT 0,y,0 (t) 2 -(1 -(y -x)tT 0,y,0 (t) 2 ) 2 -8xtT z,y,x (t) 4xtT z,y,x (t) = 1 1 -(y -x)tT 0,y,0 (t) 2 C( 2xtT z,y,x (t) (1 -(y -x)tT 0,y,0 (t) 2 ) 2 ), (2.6)
where

C(t) = 1- √ 1-4t 2t
is the generating function for Catalan numbers. Exchanging x and z in (2.6), one can compute T z,y,x (t). If one substitutes the result in (2.6), one arrives at the following proposition.

Proposition 2.1

The generating function T x,y,z (t) for GNC-trees solves the third order equation

2α 2 βx 2 tT 3 + (βz -αx)T 2 + (α 2 x -2αβz)T + α 2 βz = 0, namely, T x,y,z (t) = αC 2xtα 2 βC 2ztβ 2 T x,y,z (t) , where α = 1 1-(y-x)tT0,y,0(t) 2 and β = 1 1-(y-z)tT0,y,0(t) 2 .
By the Lagrange inversion formula and some series expansions, one can obtain the coefficient of t n of T x,y,z (t), but it seems to be somewhat complicated. Now we will consider several special cases which lead to interesting results.

u-avoiding GNC-trees

Note that T 0,y,z (t) is the generating function for GNC-trees with no ascent. By setting x = 0 in (2.5), one can find T 0,y,z (t) = 1 + ytT 0,y,0 (t) 2 T 0,y,z (t), from which, together with (2.4), and using the Lagrange inversion formula, one can deduce that

T 0,y,z (t) = T 0,y,0 (t) = n≥0 1 2n + 1 3n n (yt) n = T 0,1,0 (yt).
In fact, the above relation can be easily derived from the definition of GNC-tree: since a u-avoiding GNC-tree must also avoid the pattern d, such GNC-trees can be obtained by changing each label of the underlying NC-trees to the label 1.

h-avoiding GNC-trees

Note that T x,0,z (t) is the generating function for GNC-trees with no level. By setting y = 0 in (2.4) and (2.5), one can find

T x,0,z (t) = 1 -xtT x,0,z (t) + 2xtT x,0,z (t) 2 T z,0,x (t),
which, when x = z = 1, yields

T 1,0,1 (t) = 1 -tT 1,0,1 (t) + 2tT 1,0,1 (t) 3 . Let λ = T 1,0,1 (t) -1, then λ = t(1 + λ)(2(1 + λ) 2 -1)
, using the Lagrange inversion formula [START_REF] Wilf | Generatingfunctionology[END_REF], one can deduce for n ≥ 1 that

[t n ]T 1,0,1 (t) = [t n ]λ = 1 n [λ n-1 ](1 + λ) n (2(1 + λ) 2 -1) n = 1 n n i=0 (-1) n-i n i 2 i [λ n-1 ](1 + λ) n+2i = n i=0 (-1) n-i 2 i 2i + 1 n i n + 2i n = n i=0 (-1) n-i 2 i 2i + 1 3i i n + 2i 3i .
This leads to the following result.

Theorem 2.2

The set of h-avoiding GNC-trees of n + 1 vertices is counted by

|GNC n (h)| = n i=0 (-1) n-i 2 i 2i + 1 3i i n + 2i 3i .
This sequence beginning with 1, 1, 5, 31, 217, 1637, 12985 is listed in Sloane's [12, A153232].

d-avoiding GNC-trees

Note that T x,y,0 (t) is the generating function for GNC-trees with no descent. By setting z = 0 in (2.6), we can find

T x,y,0 (t) = 1 1 -(y -x)tT 0,y,0 (t) 2 C( 2xtT 0,y,x (t) (1 -(y -x)tT 0,y,0 (t) 2 ) 2 ), = 1 1 -(y -x)tT 0,1,0 (yt) 2 C( 2xtT 0,1,0 (yt) (1 -(y -x)tT 0,1,0 (yt) 2 ) 2 ), (2.7)
where we used the relation T 0,y,x (t) = T 0,y,0 (t) = T 0,1,0 (yt).

Case i

Setting x = y = 1 in (2.7), one gets

T 1,1,0 (t) = C(2tT 0,1,0 (t)).
Taking the coefficient t n of T 1,1,0 (t), one gets

[t n ]T 1,1,0 (t) = [t n ]C(2tT 0,1,0 (t)) = [t n ] i≥0 2 i C i t i T 0,1,0 (t) i = [t n ] i≥0 2 i C i t i j≥0 i 3j + i 3j + i j t j , = i+j=n i 3j + i 3j + i j 2 i C i .
This leads to the following results.

Theorem 2.3

The set of d-avoiding GNC-trees of n + 1 vertices is counted by

|GNC n (d)| = i+j=n i 3j + i 3j + i j 2 i C i .
This sequence beginning with 1, 2, 10, 62, 424, 3070 is not listed in Sloane's [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

Case ii

Setting y = 1 in (2.7), by (2.4), one gets

T x,1,0 (t) = T 0,1,0 (t) 1 + xtT 0,1,0 (t) 3 C( 2xtT 0,1,0 (t) 3 (1 + xtT 0,1,0 (t) 3 ) 2 ).
Taking the coefficient t n x k of T x,1,0 (t), one gets

[t n x k ]T x,1,0 (t) = [t n-k x k ] T 0,1,0 (t) 1 + xT 0,1,0 (t) 3 C( 2xT 0,1,0 (t) 3 (1 + xT 0,1,0 (t) 3 ) 2 ) = [t n-k ] k i=0 2 i C i T 0,1,0 (t) 3i+1 [x k-i ] 1 (1 + xT 0,1,0 (t)) 2i+1 = k i=0 2 i C i (-1) k-i k + i k -i [t n-k ]T 0,1,0 (t) k+2i+1 = k i=0 (-1) k-i k + i k -i k + 2i + 1 3n -2k + 2i + 1 3n -2k + 2i + 1 n -k 2 i C i .
This leads to the following results. Theorem 2. [START_REF] Flajolet | Analytic combinatorics of non-crossing configurations[END_REF] The set of d-avoiding GNC-trees of n + 1 vertices with k ascents is given by

k i=0 (-1) k-i k + i k -i k + 2i + 1 3n -2k + 2i + 1 3n -2k + 2i + 1 n -k 2 i C i .

Case iii

Setting x = 1, y = 0 in (2.7) and using T 0,0,0 (t) = T 0,1,0 (0) = 1, one gets

T 1,0,0 (t) = 1 1 + t C( 2t (1 + t) 2 ) = 1 + t - √ 1 -6t + t 2 4t ,
which is the generating function for little Schröder paths. Recall that a little Schröder path of length 2n is a lattice path in the first quadrant running from (0, 0) to (2n, 0) consisting of up steps U = (1, 1), down steps D = (1, -1) and horizontal steps H = (2, 0) with no horizontal step at the x-axis. Let S n denote the set of little Schröder paths of length 2n which is counted by the nth little Schröder number s n [12, A001003], whose generating function is

S(t) = 1+t- √ 1-6t+t 2 4t
. Theorem 2. [START_REF] Gu | 2-binary trees: bijections and related issues[END_REF] The set of {h, d}-avoiding (i.e. increasing) GNC-trees of n + 1 vertices is counted by the nth little Schröder number. There exists a bijection between GNC n (h, d) and S n .

Proof: For any T ∈ GNC n (h, d), traversing its edges from the root, when an edge (i, j) is first read, we have a U -step and mark the U -step by j; When an edge is read in the second time, we have a D-step. Then we get a little Schröder path with no H-step (In fact a Dyck path). For any U -step in the Dyck path, find the maximal segment of D-steps followed the U -step and mark all of the D-steps with the same label as the U -step. For any two consecutive steps DU (In fact a valley), if they have the same label, then replace them by an H-step and remove the remaining labels, which leads to the desired little Schröder path. It is clear that the above procedure is invertible, see Figure 2 for an example. ✷

3 The patterns in P 2

Define GNC * n (P ) to be the set of GNC-trees in GNC * n avoiding any σ in a set P of patterns. For any σ ∈ P 2 , define

T σ x,y,z (t) = n≥0 t n T ∈GNCn(σ)
x u(T ) y h(T ) z d(T ) ,

T * σ x,y,z (t) = n≥0 t n T ∈GNC * n (σ)
x u(T ) y h(T ) z d(T ) .

In this section, we deal with the patterns uu, dd, ud and du, the others can be investigated similarly.

The patterns uu and dd.

Close relations between T uu x,y,z (t) and T * uu x,y,z (t) can be established using the decomposition of GNC-trees in Figure 1. x,y,z (t) -T 0,y,0 (t). For Part III, except for the one point case, decreasing all the labels (excluding the root), by j -2 units if k = j or by j -1 units if k = j + 1, one can obtain two uu-avoiding GNC-trees in GNC * n (uu) for some n ≥ 1. Then Part III contributes 2T * uu

x,y,z (t) -1.

Case(iii): i ≥ 2, j ≥ i and k = j or j + 1. The edge (1, i ) contributes a weight of xt. Note that the ascents and descents are exchanged in Part I, and the labels are lying in {1, 2, . . . , i} or {2, 3, . . . , i}, so Part I contributes 2T dd z,y,x (t) -T 0,y,0 (t). But Part II can not begin with a u edge, i.e., all edges (if exist) starting form i are h edges, so we should further partition Part II into three parts, by finding the last vertex labeled i, which we denote by i * , in counterclockwise order such that ( i ,i * ) is an h edge which contributes a weight of yt, see Figure 3. Clearly, Part II 1 and II 2 both contribute T 0,y,0 (t), and Part II 3 contributes T uu x,y,z (t). Similar to (ii), Part III contributes 2T * uu x,y,z (t) -1. In summary, we have T uu x,y,z (t) = 1 + ytT 0,y,0 (t) 2 T uu x,y,z (t) + ytT 0,y,0 (t) T uu x,y,z (t) -T 0,y,0 (t) 2T * uu x,y,z (t) -1

String Pattern Avoidance in Generalized Non-crossing Trees

+ xt 2T dd z,y,x (t) -T 0,y,0 (t) 1 + ytT 0,y,0 (t) 2 T uu x,y,z (t) 2T * uu x,y,z (t) -1 . (3.1)
For any T ∈ GNC * n (uu), by the similar decomposition, one can easily derive that

T * uu x,y,z (t) = 1 + xtT dd z,y,x (t) 1 + ytT 0,y,0 (t) 2 T uu x,y,z (t) 2T * x,y,z (t) -1 . (3.2)
Similarly, for the pattern dd, close relations between T dd x,y,z (t) and T * dd x,y,z (t) can be established using the decomposition of GNC-trees in Figure 1, the details are omitted.

T dd

x,y,z (t) = 1 + ytT 0,y,0 (t) 2 T dd x,y,z (t) + ytT 0,y,0 (t) T dd x,y,z (t) -T 0,y,0 (t) 2T * dd x,y,z (t) -1

+ xt 2T uu z,y,x (t) -T 0,y,0 (t) T dd x,y,z (t) 2T * dd x,y,z (t) -1 , (3.3)
T * dd x,y,z (t) = 1 + xtT uu z,y,x (t)T dd x,y,z (t) 2T * dd x,y,z (t) -1 .

Solve (3.2) for T * uu x,y,z (t) and (3.4) for T * dd x,y,z (t), and then substitute them respectively into (3.1) and (3.3). After some simplifications, one obtains T uu

x,y,z (t) = 1 -xtT 0,y,0 (t) 2 + 2xtT uu x,y,z (t)T dd z,y,x (t) 1 + ytT 0,y,0 (t) 2 T uu x,y,z (t) , (3.5) T dd

x,y,z (t) = 1 + (yx)tT 0,y,0 (t) 2 T dd x,y,z (t) + 2xtT dd x,y,z (t) 2 T uu z,y,x (t).

Setting x = y = z = 1 in (3.5) and (3.6), we have Proposition 3.1 The generating functions for uu-avoiding and dd-avoiding GNC-trees are determined respectively by

T uu 1,1,1 (t) = 1 -tT 0,1,0 (t) 2 + 2tT uu 1,1,1 (t)T dd 1,1,1 (t) 1 + tT 0,1,0 (t) 2 T uu 1,1,1 (t) , T dd 1,1,1 (t) = 1 + 2tT dd 1,1,1 (t) 2 T uu 1,1,1 (t).
When x = z = 1, y = 0, by T 0,0,0 (t) = 1, (3.5) and (3.6) generate

T uu 1,0,1 (t) = 1 -t + 2tT uu 1,0,1 (t)T dd 1,0,1 (t), T dd 1,0,1 (t) = 1 -tT dd 1,0,1 (t) + 2tT dd 1,0,1 (t) 2 T uu 1,0,1 (t),
from which, one can deduce that

T uu 1,0,1 (t) = 1 -t 1 -2tT dd 1,0,1 (t) , (3.7)
T dd 1,0,1 (t) = 1 -3tT dd 1,0,1 (t) + 4tT dd 1,0,1 (t) 2 . (3.8)
From (3.7) and (3.8), one can get

T dd 1,0,1 (t) = 1 + 3t -(1 + 3t) 2 -16t 8t = 1 1 + 3t C( 4t (1 + 3t) 2 ) = i≥0 4 i C i t i (1 + 3t) 2i+1 = i≥0 4 i C i t i j≥0 (-1) j 2i + j j 3 j t j = n≥0 t n n j=0 (-1) j 2n -j j 3 j 4 n-j C n-j . T uu 1,0,1 (t) = 1 -t 1 -2tT dd 1,0,1 (t) = 3 -3t -(1 + 3t) 2 -16t 2 = 3(1 -t) -(1 -t) 2 -8t(1 -t) 2 = 1 -t + 2tC( 2t 1 -t ) = 1 + t + i≥0 2 i+2 C i+1 t i+2 (1 -t) i+1 = 1 + t + n≥0 t n+2 n i=0 n i 2 i+2 C i+1 .
This leads to the following results.

Theorem 3.2

The sets GNC n+2 (uu, h) of {uu, h}-avoiding GNC-trees and GNC n (dd, h) of {dd, h}avoiding GNC-trees are counted respectively by

|GNC n+2 (uu, h)| = n i=0 n i 2 i+2 C i+1 , |GNC n (dd, h)| = n j=0 (-1) j 2n -j j 3 j 4 n-j C n-j , ([12, A059231]).
Remark 3. 3 Coker [2] proved that T dd 1,0,1 (t) is also the generating function for D n , the set of different lattice paths running from (0, 0) to (2n, 0) using steps from S = {(k, ±k) : k positive integer} that never go below x-axis, and provided several different expressions for |D n |. One may ask to find a bijection between D n and GNC n (dd, h).

The patterns ud and du

Similar to Subsection 3.1, close relations between T ud x,y,z (t) and T * ud x,y,z (t), and between T du x,y,z (t) and T * du

x,y,z (t), can be derived using the decomposition of GNC-trees, see Figure 1, but the details are omitted.

T ud x,y,z (t) = 1 + ytT 0,y,0 (t)

Solve (3.10) for T * ud x,y,z (t) and (3.12) for T * du x,y,z (t), and then substitute them respectively into (3.9) and (3.11). After some simplifications, one obtains T ud

x,y,z (t) = 1 + (yx)tT 0,y,0 (t) 2 T ud x,y,z (t) + 2xtT ud x,y,z (t) 2 1 + ytT 0,y,0 (t) 2 T du z,y,x (t) , (3.13) T du

x,y,z (t) = 1 + (yx)tT 0,y,0 (t) 2 T du x,y,z (t) + 2xtT du x,y,z (t) 2 T ud z,y,x (t).

(3.14)

The case x = y = z = 1 in (3.13) and (3.14) yields the following result.

Proposition 3.4

The generating functions for ud-avoiding and du-avoiding GNC-trees are given by

T ud 1,1,1 (t) = 1 + 2tT ud 1,1,1 (t) 1 + tT 0,1,0 (t) 2 T du 1,1,1 (t) , T du 1,1,1 (t) = 1 + 2tT du 1,1,1 (t) 2 T ud 1,1,1 (t).
When x = z = 1, y = 0, by T 0,0,0 (t) = 1, (3.13) and (3.14) generate

T ud 1,0,1 (t) = 1 -tT ud 1,0,1 (t) + 2tT ud 1,0,1 (t) 2 , T du 1,0,1 (t) = 1 -tT du 1,0,1 (t) + 2tT du 1,0,1 (t) 2 T ud 1,0,1 (t),
from which, one can deduce that

T ud 1,0,1 (t) = S(t) = 1 + t - √ 1 -6t + t 2 4t = 1 1 + t C( 2t (1 + t) 2 ), T du 1,0,1 (t) = 1 + t -(1 + t) 2 -8tS(t) 4tS(t) = 1 1 + t C( 2tS(t) (1 + t) 2 ) = i≥0 2 i C i S(t) i t i (1 + t) 2i+1 = i≥0 2 i C i t i (1 + t) 3i+1 C( 2t (1 + t) 2 ) i = i≥0 2 i C i t i (1 + t) 3i+1 j≥0 i 2j + i 2j + i j 2 j t j (1 + t) 2j = n≥0 t n i+j+k=n (-1) k 3i + 2j + k k i 2j + i 2j + i j 2 i+j C i .
This leads to the following result.

Theorem 3.5

The set GNC n (ud, h) of {ud, h}-avoiding (i.e. increasing) GNC-trees is counted by the nth little Schröder number, and the set GNC n (du, h) of {du, h}-avoiding GNC-trees is counted by

|GNC n (du, h)| = i+j+k=n (-1) k 3i + 2j + k k i 2j + i 2j + i j 2 i+j C i .
This sequence beginning with 1, 1, 5, 27, 157, 957, 6025 is listed in [12, A153233].

The pattern {uu, dd}

Now we consider the pattern {uu, dd}, let P = {uu, dd}, using the decomposition of GNC-trees, relations between T P x,y,z (t) and T * P x,y,z (t) can be derived, the details are omitted:

T P x,y,z (t) = 1 + ytT 0,y,0 (t) 2 T P x,y,z (t) + ytT 0,y,0 (t) T P x,y,z (t) -T 0,y,0 (t) 2T Setting z = 1 in (3.18), one can deduce (-1)

T P x,0,1 (t) = 1 + 2(1 -x)t -(1 + 2(1 -x)t) 2 -8t(1 -xt) 4t = 1 -xt 1 + 2(1 -x)t C( 2t(1 -xt) (1 + 2(1 -x)t) 2 ) = i≥0 2 i C i t i (1 -xt) i+1 (1 + 2(1 -x)t) 2i+1 = i≥0 2 i C i t i i+1 j=0 (-1) j i + 1 j x j t j k≥0 (-1) k 2i + k k 2 k t k k ℓ=0 ( -
n-i i + 1 n -i 2 i C i , ([12, A068764]).
Moreover, the number of alternating GNC-trees of n + 1 vertices with exactly r ascents is i+j+k=n (-1) r+k i + 1

j 2i + k k k r -j 2 i+k C i .

Fig. 1 :

 1 Fig. 1: Decomposition of GNC-trees.

Fig. 2 :

 2 Fig. 2:The bijection between GNCn(h, d) and Sn.

  Case(i): i = j = 1 and k = 1 or 2. Part I and II both avoid the patterns u and d, Part III still forms a uuavoiding GNC-tree. Then the edge (1, 1) contributes a weight of yt, each of Part I and II contributes T 0,y,0 (t), and Part III contributes T uu x,y,z (t). Case(ii): i = 1, j ≥ 2 and k = j or j + 1. Part I avoids the patterns u and d, Part II still forms a uu-avoiding GNC-tree, where not all vertices are labeled by 1. Then the edge (1, 1) contributes a weight of yt, Part I contributes T 0,y,0 (t) and Part II contributes T uu

Fig. 3 :

 3 Fig. 3: The decomposition of Part II in (iii).

2 (- 1 )Theorem 3 . 7

 2137 i+k C i .Setting x = z = 1 in (3.18), one hasT P 1,0,1 (t) = 1 -1 -8t(1t) 4t = (1t)C(2t(1t)) n-i i + 1 ni 2 i C i ,which leads to the following result. The number of {uu, dd, h}-avoiding (i.e., alternating) GNC-trees of n + 1 vertices is given by n i=0

  ytT 0,y,0 (t) 2 T P x,y,z (t) 1 -xtT 0,y,0 (t) 2 + 2xtT P z,y,x (t)T P x,y,z (t) . (3.15)The case x = y = z = 1 in (3.15) yields Proposition 3.[START_REF] Hough | Descents in noncrossing trees[END_REF] The generating function for {uu, dd}-avoiding GNC-trees is given byT P 1,1,1 (t) = 1 + tT 0,1,0 (t) 2 T P 1,1,1 (t) 1 -tT 0,1,0 (t) 2 + 2tT P 1,1,1 (t) 2 .String Pattern Avoidance in Generalized Non-crossing Trees91Setting y = 0 in (3.15), by T 0,0,0 (t) = 1, one can get T P x,0,z (t) = 1xt + 2xtT P z,0,x (t)T P x,0,z (t).

	from which, one can get T P x,y,z (t) = Exchanging x and z in (3.16), one has T P z,0,x (t) = 1 -zt + 2ztT P x,0,z (t)T P z,0,x (t). From (3.16) and (3.17), one can obtain T P x,0,z (t) = 1 -xt -2(z -x)tT P x,0,z (t) + 2ztT P x,0,z (t) 2 , which leads to 1 + (3.16) (3.17) T P x,0,z (t) = 1 + 2(z -x)t -(1 + 2(z -x)t) 2 -8zt(1 -xt) 4zt . (3.18)

* P x,y,z (t) -1 + xt 2T P z,y,x (t) -T 0,y,0 (t) 1 + ytT 0,y,0 (t) 2 T P x,y,z (t) 2T * P x,y,z (t) -1 , T * P x,y,z (t) = 1 + xtT P z,y,x (t) 1 + ytT 0,y,0 (t) 2 T P x,y,z (t) 2T * P x,y,z (t) -1 ,

Acknowledgements

The authors are grateful to the anonymous referees for the helpful suggestions and comments. The work was supported by The National Science Foundation of China (10801020).

Yidong Sun and Zhiping Wang

Remark 3.8 When r = 0, then j = 0 and there is no alternating GNC-tree of n + 1 vertices with exactly r = 0 ascents for n ≥ 1. So we have

When x = -1, z = 1 in (3.18), one has

which leads to the following results.

Theorem 3.9 The difference between the number of alternating GNC-trees on m vertices with an even number of ascents and those with an odd number of ascents is zero if m = 2n + 3 and (-1) n+1 2 n C n if m = 2n + 2 for n ≥ 0.


Jan Foniok
email: foniok@math.ethz.ch

Claude Tardif
email: claude.tardif@rmc.ca

Adjoint functors and tree duality

Keywords: 2000 Mathematics Subject Classification: 16B50, 68R10, 18A40, 05C15 constraint satisfaction, tree duality, adjoint functor

A family T of digraphs is a complete set of obstructions for a digraph H if for an arbitrary digraph G the existence of a homomorphism from G to H is equivalent to the non-existence of a homomorphism from any member of T to G.

A digraph H is said to have tree duality if there exists a complete set of obstructions T consisting of orientations of trees. We show that if H has tree duality, then its arc graph δH also has tree duality, and we derive a family of tree obstructions for δH from the obstructions for H.

Furthermore we generalise our result to right adjoint functors on categories of relational structures. We show that these functors always preserve tree duality, as well as polynomial CSPs and the existence of near-unanimity functions.

Introduction

Our primary motivation is the H-colouring problem (which has become popular under the name Constraint Satisfaction Problem-CSP): for a fixed digraph H (a template) decide whether an input digraph G admits a homomorphism to H. The computational complexity of H-colouring depends on the template H. For some templates the problem is known to be NP-complete, for others it is tractable (a polynomial-time algorithm exists). Assuming that P = NP, infinitely many complexity classes lie strictly between P and NP [START_REF] Ladner | On the structure of polynomial time reducibility[END_REF], but it has been conjectured that H-colouring belongs to no such intermediate class for any template H [START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory[END_REF]. This conjecture has indeed been proved for symmetric templates H [START_REF] Hell | On the complexity of H-coloring[END_REF].

In this paper the focus is on tractable cases. Several conditions are known to imply the existence of a polynomial-time algorithm for H-colouring (definitions follow in the next two paragraphs): it is the case if H has a near-unanimity function (nuf), if H has bounded-treewidth duality, if H has tree duality, if H has finite duality (see [START_REF] Cohen | The complexity of constraint languages[END_REF][START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory[END_REF][START_REF] Hell | Duality and polynomial testing of tree homomorphisms[END_REF]). Some of the conditions are depicted in the diagram (Fig. 1).

A near-unanimity function is a homomorphism f from H k to H with k ≥ 3 such that for all x, y ∈ V (H) we have f (x, x, x, . . . , x) = f (y, x, x, . . . , x) = f (x, y, x, . . . , x) = • • • = f (x, x, x, . . . , y) = x. The power H k is the k-fold product H × H × • • • × H in the category of digraphs and homomorphisms, see [START_REF] Hell | Graphs and Homomorphisms[END_REF].

A digraph is a tree (has treewidth k) if its underlying undirected graph is a tree (has treewidth k, respectively). A set F of digraphs is a complete set of obstructions for H if for an arbitrary digraph G there exists a homomorphism from G to H if and only if no F ∈ F admits a homomorphism to G. A template has bounded-treewidth duality if it has a complete set of obstructions with treewidth bounded by a constant; it has tree duality if it has a complete set of obstructions consisting of trees; and it has finite duality if it has a finite complete set of obstructions.

There is a fairly straightforward way to generate templates with finite duality. For an arbitrary tree T there exists a digraph D(T ) such that {T } is a complete set of obstructions for D(T ). The digraph D(T ) is unique up to homomorphic equivalence (i) ; it is called the dual of T . Several explicit constructions are known (see [START_REF] Foniok | Homomorphisms and Structural Properties of Relational Systems[END_REF][START_REF] Komárek | Good characterisations in the class of oriented graphs[END_REF][START_REF] Nešetřil | Duality theorems for finite structures (characterising gaps and good characterisations)[END_REF][START_REF] Nešetřil | Short answers to exponentially long questions: Extremal aspects of homomorphism duality[END_REF]). If F is a finite set of oriented trees, then the product D = T ∈F D(T ) is a template with finite duality and F is a complete set of obstructions for D. This construction yields all digraphs with finite duality [START_REF] Nešetřil | Duality theorems for finite structures (characterising gaps and good characterisations)[END_REF], thus also proving that finite duality implies tree duality.

Encouraged by the full description of finite dualities, we aim to provide a construction for some more digraphs with tree duality. To this end we use the arc-graph construction and consider the class δ π C of digraphs generated from finite duals by taking iterated arc graphs and finite Cartesian products. We show that all templates in this class have tree duality. We provide an explicit construction of the resulting tree obstructions, which allows us to show that all the digraphs in δ π C have in fact bounded-height tree duality, that is, they have a complete set of obstructions consisting of trees of bounded algebraic height (these are (i) Two digraphs H and H ′ are homomorphically equivalent if there exists a homomorphism from H to H ′ as well as a homomorphism from H ′ to H. Clearly, if H and H ′ are homomorphically equivalent, then H-colouring and H ′ -colouring are equivalent problems, because H and H ′ admit homomorphisms from exactly the same digraphs. tree obstructions that allow a homomorphism to a fixed directed path). In this context we also prove that the problem of existence of a complete set of obstructions consisting of trees with bounded algebraic height is decidable.

The arc-graph construction is a special case of a more general phenomenon: it is a right adjoint in the category of digraphs and homomorphisms. We show in the more general setting of the category of relational structures that right adjoints (characterised by Pultr [START_REF] Pultr | The right adjoints into the categories of relational systems[END_REF] for all locally presentable categories) preserve tractability of templates and moreover they preserve tree duality and existence of a near-unanimity function. In this case, nevertheless, it remains open to provide a nice general description of complete sets of obstructions.

We use some notions and properties of graphs and homomorphisms which the reader can look up in [START_REF] Hell | Graphs and Homomorphisms[END_REF], as well as some category-theory notions, for which, e.g. [START_REF] Barr | Category Theory for Computing Science[END_REF][START_REF] Lane | Categories for the Working Mathematician, volume 5 of Graduate texts in mathematics[END_REF] may be consulted.

Arc graphs and tree duality

Let G = (V, A) be a digraph. The arc graph of G is the digraph δG = (A, δA), where

δA = ((u, v), (v, w)) : (u, v), (v, w) ∈ A .
Notice that δ is an endofunctor (i) in the category of digraphs and homomorphisms. This implies in particular that if G → H, then δG → δH. (The notation G → H means that there exists a homomorphism from G to H.)

If G is a digraph and ∼ is an equivalence relation on its vertex set

V (G), the quotient G/∼ is the digraph (V (G)/∼, A), where V (G)/∼ is the set of all equivalence classes of ∼ on V (G), and for X, Y ∈ V (G)/∼ we have (X, Y ) ∈ A if and only if there exist x ∈ X and y ∈ Y such that (x, y) ∈ A(G). Suppose still that G = (V, A) is a digraph. Let V ′ = {o u , t u : u ∈ V } and let A ′ = {(o u , t u ) : u ∈ V }. Define the relation ∼ 0 such that t u ∼ 0 o v if and only if (u, v) ∈ A. Let ∼ be the minimal equivalence relation on V ′ containing ∼ 0 . Set δ -1 G = (V ′ , A ′ )/∼.
In the following, we use the notation V ′ (G) = V ′ , A ′ (G) = A ′ and ∼ 0 and ∼ for the sets and relations appearing in the definition of δ -1 ; the precise meaning will be clear from the context. Now δ -1 is also an endofunctor in the category of digraphs. Strictly speaking, it is not an inverse of δ; its name is chosen because of the following property.

G → H such that f (u) = (o(u), t(u)) for all u ∈ V (G). Define the mapping ĝ : V ′ (G) → V (H) by ĝ(o u ) = o(u) and ĝ(t u ) = t(u). If t u ∼ 0 o v , then (u, v) ∈ A(G), whence (f (u), f (v)) ∈ A(δH) and thus t(u) = o(v)
. Therefore ĝ is constant on the equivalence classes of ∼, and it induces a homomorphism from

A ′ (G)/∼ = δ -1 G to H. Conversely, let g : δ -1 G → H be a homomorphism. We define f : V (G) → V (δH) by f (u) = (g(o u /∼), g(t u /∼)). If (u, v) ∈ A(G), then t u /∼ = o v /∼, whence (f (u), f (v)) ∈ A(δH). Therefore f is a homomorphism. ✷ (i)
An endofunctor is a functor from a category to itself.

Thus δ and δ -1 are Galois adjoints (i) with respect to the ordering by existence of homomorphisms. They are in fact adjoint functors in the category of digraphs and homomorphisms. We return to this topic in Section 4. For the moment we aim to prove that δ preserves tree duality. More precisely, from the family T of tree obstructions of H, we will derive the family Sproink(T ) of tree obstructions of δH.

The algebraic height of an oriented tree T is the minimum number of arcs of a directed path to which T maps homomorphically. The algebraic height of every finite oriented tree is well-defined and finite, since every such tree admits a homomorphism to some finite directed path. Thus a tree T is of height at most one if its vertex set can be split into two parts 0 T , 1 T in such a way that for every arc (x, y) of T we have x ∈ 0 T and y ∈ 1 T . Note that if the tree T has no arcs, then it has only one vertex and thus one of the sets 0 T , 1 T is empty and the other one is a singleton.

Let T be a tree. For every vertex u of T , let F (u) be a tree of height at most one. For each arc e of T incident with u, let there be a fixed vertex v(e, F (u)) in F (u) such that if u is the initial vertex of e, then v(e, F (u)) ∈ 1 F (u) , and if u is the terminal vertex of e, then v(e, F (u)) ∈ 0 F (u) . (ii) A tree S is now constructed by taking all the trees F (u) for all vertices u of T , and by identifying the vertex v(e, F (u)) with v(e, F (u ′ )) whenever e = (u, u ′ ) is an arc of T .

Any such tree S constructed from T by the above procedure is called a sproink of T . The set of all sproinks of a tree T is denoted by Sproink(T ). The following lemma asserts that sproinks of obstructions for a template H are indeed obstructions for its arc graph δH.

Lemma 2 Let T be a tree and H a digraph such that T H. If S ∈ Sproink(T ), then S δH.

Proof: We prove that T → δ -1 S. Consequently δ -1 S H because T H, and therefore S δH by Proposition 1.

Thus let S ∈ Sproink(T ). For a vertex u of T , consider the tree F (u), which is a subgraph of S. Since F (u) has height at most one, its vertices are partitioned into the sets 0 F (u) and 1 F (u) . The set V ′ (S), which appears in the definition of δ -1 S, contains V ′ (F (u)) as a subset. If (x, y) is an arc of F (u), then t x ∼ 0 o y . Thus whenever x ∈ 0 F (u) and y ∈ 1 F (u) , then t x ∼ o y . Hence for any vertex u of T there exists a unique vertex f (u) of δ -1 S that is equal to t x /∼ for all x ∈ 0 F (u) and to o y /∼ for all y ∈ 1 F (u) .

In this way, we have defined a mapping f : V (T ) → V (δ -1 S). Now assume that e = (u, v) is an arbitrary arc of T . Then the vertex v(e, F (u)), which belongs to 1 F (u) , has been identified with v(e, F (v)), which belongs to 0 F (v) . Let this identified vertex be x; it is a vertex of S. By definition,

f (u) = o x /∼ because x ∈ 1 F (u) , and f (v) = t x /∼ because x ∈ 0 F (v) . Of course (o x /∼, t x /∼) ∈ A(δ -1 S). Therefore f : T → δ -1 S is a homomorphism, as we have promised to prove. ✷ For a set F of trees, let Sproink(F) = T ∈F Sproink(T ).
Theorem 3 Let F be a set of trees which is a complete set of obstructions for a template H. Then Sproink(F) is a complete set of obstructions for δH.

(i) Let X and Y be partially ordered sets. Mappings φ : X → Y and ψ : Y → X are Galois adjoints if φ(x) ≤ Y y ⇔ x ≤ X ψ(y) for all elements x ∈ X and y ∈ Y .

(ii) It follows that if u is neither a source nor a sink of T , then both 0 F (u) and 1 F (u) are non-empty, and so in this case F (u) is not a single vertex. If u is a source or a sink of T , then F (u) may be an arbitrary tree of height at most one. Proof: Lemma 2 implies that Sproink(F) is a set of obstructions for δH. It remains to prove that it is complete, that is whenever G δH, then there exists some S ∈ Sproink(F) such that S → G. So let G δH. Thus by Proposition 1 we have δ -1 G H. Hence there exists a tree T ∈ F such that T → δ -1 G, because F is a complete set of obstructions for H. Consequently it suffices to prove that if T → δ -1 G then there exists S ∈ Sproink(T ) such that S → G.

Thus assume that f :

T → δ -1 G is a homomorphism. For every u ∈ V (T ), the image f (u) is a ∼-equivalence class; put 1 u = {y ∈ V (G) : o y ∈ f (u)}, 0 u = {x ∈ V (G) : t x ∈ f (u)}.
Then f (u) = 1 u ∪ 0 u , and by the definition of ∼ as the least equivalence containing ∼ 0 , there exists a tree F (u) of height at most one and a homomorphism g u :

F (u) → G such that g u (0 F (u) ) = 0 u and g u (1 F (u) ) = 1 u . For every arc (u, v) of T , we have (f (u), f (v)) ∈ A(δ -1 G) so there exists x ∈ V (G) such that o x ∈ f (u) and t x ∈ f (v).
We then select y ∈ 1 F (u) and z ∈ 0 F (v) such that g u (y) = g v (z) = x, and identify them. Proceeding with all such identifications, we construct a tree S ∈ Sproink(T ) such that g = u∈V (T ) g u : S → G is a well-defined homomorphism. ✷

Corollary 4 If a digraph H has tree duality, then its arc graph δH also has tree duality. ✷ Example 1 Consider T = P 4 , the directed path with four arcs, and its dual D = T 4 , the transitive tournament on four vertices. Here δD has six vertices, but its core (i) is the directed path P 2 with two arcs. It is well known that a directed graph G admits a homomorphism to P 2 if and only if it does not admit a homomorphism from a "thunderbolt", that is, an oriented path with two forward arcs at the beginning and at the end, and with an odd-length alternating path between them (see Fig. 2). Thus the family of all thunderbolts is a complete set of tree obstructions for P 2 .

Our construction Sproink(T ) gives all obstructions obtained by stacking five trees L 0 , L 1 , L 2 , L 3 , L 4 of height at most one, with one top vertex of L i identified with one bottom vertex of L i+1 for i = 0, 1, 2, 3.

(i) The core of a digraph is any of its smallest subgraphs to which it admits a homomorphism. Every digraph H has a unique core C (up to isomorphism), which is moreover the only core homomorphically equivalent to it. In fact, the core C of H is a retract of H, which means that there exists a homomorphism ρ : H → C whose restriction on C is the identity mapping (such a homomorphism is called a retraction).

The example of thunderbolts shows that in fact L 0 can be restricted to a single (top) vertex, and L 4 can be restricted to a single (bottom) vertex. The same holds for leaves of general trees. Also, L 1 , L 2 , L 3 can be restricted to paths of height one, and it is also true in general that it is sufficient to consider sproinks obtained by replacing vertices by paths of height at most one. In fact the name "sproink" is inspired by picturing such a path springing out of every non-leaf of T .

The results of this section show that we can construct an interesting class of templates with tree duality by repeatedly applying the arc-graph construction to digraphs with finite duality. Moreover, if templates H 1 , H 2 , . . . , H k all have tree duality, then also their product

H 1 × H 2 × • • • × H k
has tree duality as the union of the respective complete sets of obstructions of the factors is a complete set of obstructions for the product. The resulting class of templates is subject to examination in the next section.

Finite duality

Following [START_REF] Nešetřil | Duality theorems for finite structures (characterising gaps and good characterisations)[END_REF], every tree T admits a dual D(T ) such that for every digraph G, we have G → D(T ) if and only if T G. A digraph H has finite duality if and only if it is homomorphically equivalent to a finite product of duals of trees.

In this section, we consider the class δ π C, the smallest class of digraphs that contains all duals of trees and is closed under taking arc graphs, finite products and homomorphically equivalent digraphs. It follows from Corollary 4 that all elements of δ π C have tree duality. Moreover we know how to construct a complete set of obstructions for each of these templates, using iterated Sproink constructions and unions. The question then arises as to how significant the class δ π C is within the class of digraphs with tree duality. It turns out that the digraphs in δ π C have properties that are not shared by all digraphs with tree duality.

A digraph H has bounded-height tree duality provided there exists a constant m such that H admits a complete set of obstructions consisting of trees of algebraic height at most m.

Proposition 5 (i) Every core in δ π C admits a near-unanimity function.

(ii) Every member of δ π C has bounded-height tree duality.

Proof: (i): By Corollary 4.5 of [START_REF] Larose | A characterisation of first-order constraint satisfaction problems[END_REF], every structure with finite duality admits a near-unanimity function. Therefore it suffices to show that the class of structures admitting a near-unanimity function is closed under taking cores, finite products and the arc-graph construction.

Let C be the core of H, ρ : H → C a retraction and f :

H k → H a near-unanimity function. Since C is an induced subgraph of H, the restriction ρ • f ↾ C k is a near-unanimity function on C. Suppose f i : H ki i → H i , i = 1, .
. . , m are near-unanimity functions. For k = max{k i : i = 1, . . . , m}, we define k-ary near-unanimity functions g i :

H k i → H i by g i (x 1 , . . . , x k ) = f i (x 1 , . . . , x ki ). For H = Π m i=1 H i we
, v k )) = (f (u 1 , . . . , u k ), f (v 1 , . . . , v k )).
The fact that f is a homomorphism implies that g is well defined, and g is a homomorphism by the definition of adjacency in δH. Also, g clearly satisfies the near-unanimity identities, so it is a nearunanimity function on δH.

(ii): The class of digraphs with bounded-height tree duality is obviously preserved by taking cores and finite products. By Theorem 3, if H has a complete set of obstructions consisting of trees of algebraic height at most k, then δH has a complete set of obstructions consisting of trees of algebraic height at most k + 1, so the class of digraphs with bounded-height tree duality is also preserved by the arc-graph construction.

✷

We know a core digraph with tree duality but no near-unanimity function and no bounded-height tree duality. (The example is complicated and out of the scope of this paper, therefore we omit it.) Thus the class δ π C does not capture all core digraphs with tree duality. The problem of generating all structures with tree duality by means of suitable functors applied to structures with finite duality remains nevertheless interesting.

Membership in δ π C is not known to be decidable. In the remainder of this section, we show that bounded-height tree duality is decidable.

Given a digraph H, the n-th crushed cylinder H * n is the quotient (H 2 × P n )/≃ n , where P n is the path with arcs (0, 0), (0, 1), (1, 2), • • • , (n -1, n), (n, n), and ≃ n is the equivalence defined by

(u, v, i) ≃ n (u ′ , v ′ , j) ⇔      i = j = 0 and u = u ′ , or i = j = n and v = v ′ , or (u, v, i) = (u ′ , v ′ , j).
Theorem 6 For a core digraph H with tree duality, the following are equivalent:

(1) H has bounded-height tree duality,

(2) For some n we have H * n → H.

(3) There exists a directed (upward) path from the first projection to the second in H H 2 .

Proof: (1) ⇒ (2): The two subgraphs obtained from H * n by removing the two ends both admit homomorphisms to H. Therefore, if a tree obstruction of H admits a homomorphism to H * n , its image must intersect the two ends hence its algebraic length must be at least n.

¬(1) ⇒ ¬(2): Let T be a critical obstruction of H of algebraic length n + 2. Let T 0 , T n be the subgraphs of T obtained by removing the vertices of height 0 and n + 2 respectively. Then there exists homomorphisms f 0 : T 0 → H and f n : T n → H. Let h : T → P n+2 be the height function of T . We define a map f :

T → H * n by f (u) =      (f n (u), f 0 (u), h(u) -1)/≃ n if h(u) ∈ {0, n + 2}, (f n (u), f n (u), 0)/≃ n if h(u) = 0, (f 0 (u), f 0 (u), n)/≃ n if h(u) = n + 2.
Let (u, v) be an arc of T . Then

h(v) = h(u) + 1. If {h(u), h(v)} ∩ {0, n + 2} = ∅, we clearly have (f (u), f (v)) ∈ A(H * n ). If h(u) = 0, then f (u) = (f n (u), f n (u), 0)/≃ n is an in-neighbour of (f n (v), f n (v), 0)/≃ n = (f n (v), f 0 (v), 0)/≃ n = f (v), and if h(v) = n+2, f (v) = (f 0 (v), f 0 (v), n)/≃ n is an out-neighbour of f (u) because (f 0 (u), f 0 (u), n)/≃ n = (f n (u), f 0 (u), n)/≃ n = f (u).
Therefore f is a homomorphism.

(2) ⇔ (3): This equivalence follows easily from the definition. ✷

Corollary 7

The problem whether an input digraph has bounded-height tree duality is decidable.

Proof: It is decidable whether a digraph has tree duality [START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory[END_REF] (see Theorem 11 below). For a digraph with tree duality, bounded height of the obstructions (the condition (1) of Theorem 6) is equivalent to the condition (3), which involves directed reachability in a finite graph. Hence bounded-height tree duality is decidable. ✷

Adjoint functors and generation of tractable templates

The correspondence of Proposition 1 can be extended to a wide class of functors presented in this section.

To illustrate this extension, we first redefine δ in terms of patterns. Let P be the digraph with vertices 0, 1 and arc (0, 1), and Q the digraph with vertices 0, 1, 2 and arcs (0, 1), [START_REF] Barr | Category Theory for Computing Science[END_REF][START_REF] Cohen | The complexity of constraint languages[END_REF]. Furthermore let q 1 , q 2 : P → Q be the homomorphisms mapping the arc (0, 1) to (0, 1) and (1, 2) respectively. For an arbitrary digraph G, its arc graph δG can be described as follows: The vertices of δG are the arcs of G, that is, the homomorphisms f : P → G. The arcs of δG are the couples of consecutive arcs in G, that is, the couples (f 1 , f 2 ) such that there exists a homomorphism g : Q → G satisfying g • q 1 = f 1 and g • q 2 = f 2 . Thus the functor δ is generated by the pattern {P, (Q, q 1 , q 2 ))} in a way that generalises quite naturally. The rest of this section deals with relational structures. A vocabulary is a finite set σ = {R 1 , . . . , R m } of relation symbols, each with an arity r i assigned to it. A σ-structure is a relational structure A = A; R 1 (A), . . . , R m (A) where A is a non-empty set called the universe of A, and R i (A) is an r i -ary relation on A for each i. Homomorphisms of relational structures are relation-preserving mappings between universes; a homomorphism is defined only between structures with the same vocabulary. Cores, trees, quotient structures, etc. can also be defined in the context of relational structures, consult [START_REF] Loten | Majority functions on structures with finite duality[END_REF] for the details (see also [START_REF] Hodges | A shorter model theory[END_REF][START_REF] Larose | A characterisation of first-order constraint satisfaction problems[END_REF]). The notions of the constraint satisfaction problem, template, and tree duality also carry over naturally from the setting of digraphs.

Let σ and τ be two vocabularies. Let P be a σ-structure, and for every relation R of τ of arity r = a(R), let Q R be a σ-structure with r fixed homomorphisms q R,i : P → Q R for i = 1, . . . , r. Then the family {P } ∪ {(Q R , q R,1 , . . . , q R,a(R) ) : R ∈ τ } defines a functor Ψ from the category A of σ-structures to the category B of τ -structures as follows.

• For a σ-structure A, let B = ΨA be a τ -structure whose universe is the set of all homomorphisms f : P → A.

• For every relation R of τ of arity r = a(R), let R(B) be the set of r-tuples (f 1 , . . . , f r ) such that there exists a homomorphism g : Q R → A such that for i = 1, . . . , r we have g • q R,i = f i .

Proof of Theorem 10: Suppose A has tree duality. Then there is a homomorphism f : UA → A. Let U = P(ΨA) \ {∅} be the universe of UΨA and let S ∈ U . For p ∈ P , define S p = {f (p) : f ∈ S} ∈ UA, and f S (p) = f (S p ). We claim that f S : P → A is a homomorphism. Indeed, for R ∈ σ and (p 1 , . . . , p r ) ∈ R(P ), the r-tuples (f (p 1 ), . . . , f (p r )) ∈ R(A) for all f ∈ S prove that (S p1 , . . . , S pr ) ∈ R(UA), whence (f S (p 1 ), . . . , f S (p r )) = (f (S p1 ), . . . , f (S pr )) ∈ R(A).

Thus we define a map f : UΨA → ΨA by f (S) = f S . We show that it is a homomorphism. For R ∈ τ and (S 1 , . . . , S r ) ∈ R(UΨA), every f i ∈ S i , 1 ≤ i ≤ r is contained in an r-tuple (h 1 , . . . , h r ) ∈ R(ΨA) with f j ∈ S j for 1 ≤ j ≤ r and h i = f i , whence there exists a homomorphism g (h1,...,hr) : Q R → A such that h j = g (h1,...,hr) • q R,j for j = 1, . . . , r. For x ∈ Q, let T x be the set of all images g (h1,...,hr) (x) ∈ A (with (S 1 , . . . , S r ) fixed), and g (S1,...,Sr) (x) = f (T x ). Then g (S1,...,Sr) : Q R → A is a homomorphism, and for x ∈ q R,j (P ) we have T x = S x (because they are images of x under restrictions of the same homomorphisms), whence g (S1,...,Sr) (x) = f Sj (x). Thus f Sj = g (S1,...,Sr) • q R,j for j = 1, . . . , r. Consequently (f S1 , . . . , f Sr ) = ( f (S 1 ), . . . , f (S r )) ∈ R(ΨA). This shows that f is a homomorphism. ✷

Unlike the case of the arc-graph construction, we are unable to provide an explicit description of the tree obstructions of ΨA in terms of those of A for a general right adjoint Ψ. However, in isolated cases we can do it, as the following example shows.

Example 2

The endofunctor Ψ on the category of digraphs is defined via the pattern {P, (Q, q 1 , q 2 )}, where P = P 1 is the one-arc path u → v, Q = P 3 is the directed path 0 → 1 → 2 → 3, the homomorphism q 1 : u → 0, v → 1, and finally q 2 : u → 2, v → 3.

Let T be a tree of algebraic height h and consider the unique homomorphism t from T to the directed path P h . The arcs of T are of two kinds: blue arcs A b (T ) = {(x, y) : t(x) = 2k, t(y) = 2k + 1 for some integer k} and red arcs A r (T ) = {(x, y) : t(x) = 2k + 1, t(y) = 2k + 2 for some integer k}. We define two equivalence relations on the vertices of T : x ∼ b y if the (not necessarily directed) path from x to y in T has only blue arcs, and x ∼ r y if the path from x to y in T has only red arcs. Then T has two Ψ-Sproinks, namely T /∼ b and T /∼ r with loops removed.

For a collection T of trees, let Ψ-Sproink(T ) be the set of all Ψ-Sproinks of the trees contained in T . We claim that if T is a complete set of obstructions for a template H, then Ψ-Sproink(T ) is a complete set of obstructions for ΨH. To prove it, we follow the idea of the proofs of Lemma 2 and Theorem 3.

First we prove that T → Ψ -1 (T /∼ b ). This is not difficult: every blue arc of T was contracted to a vertex of T /∼ b and this vertex was blown up to an arc in T → Ψ -1 (T /∼ b ). Thus we can map blue arcs to the corresponding blown-up arcs. Red arcs of T are also arcs of T /∼ b , and hence we can map each red arc to the arc (1, 2) of the corresponding copy of Q in Ψ -1 (T /∼ b ). Clearly such a mapping is a homomorphism.

Analogously we show that T → Ψ -1 T /∼ r . Finally we want to prove that if

T → Ψ -1 G, then either T /∼ b → G or T /∼ r → G. Suppose that f : T → Ψ -1 G.
Then some arcs of T are mapped by f to arcs corresponding to vertices of G (arcs of copies of P ), and others are mapped to arcs corresponding to arcs of G (arcs (1, 2) of copies of Q). Let us call the former v-arcs and the latter a-arcs. It follows from the definition of Ψ -1 that either all blue arcs of T are v-arcs and all red arcs of T are a-arcs, or all blue arcs of T are a-arcs and all red arcs of T are v-arcs. In the former case T /∼ b → G, while in the latter case T /∼ r → G.

It is notable that in the above example each tree obstruction for H generates finitely many obstructions for ΨH. This is no accident.

Theorem 12 Let Ψ be a functor generated by a pattern {P } ∪ {(Q R , q R,1 , . . . , q R,a(R) ) : R ∈ τ }, where for every R ∈ τ and 1 ≤ i < j ≤ a(R), the image q R,i (P ) is vertex-disjoint from q R,j (P ). If a σ-structure A has finite duality, then the τ -structure ΨA also has finite duality.

The proof uses the characterisation of structures with finite duality of [START_REF] Larose | A characterisation of first-order constraint satisfaction problems[END_REF]. The square of a σstructure B is the structure B × B. It contains the diagonal ∆ B×B = {(b, b) : b ∈ B}. An element a of B is dominated by an element b of B if for every R ∈ σ, for every i and every (x 1 , . . . , x a(R) ) ∈ R(B) with x i = a, we have (y 1 , . . . , y a(R) ) ∈ R(B) with y i = b and y j = x j for j = i. A structure B dismantles to its induced substructure C if there exists a sequence x 1 , . . . , x k of distinct elements of B such that B \ C = {x 1 , . . . , x k } and for each 1 ≤ i ≤ k the element x i is dominated in the structure induced by C ∪ {x i , . . . , x k }. The sequence x 1 , . . . , x k is then called a dismantling sequence of B on C.

Theorem 13 ([11]) A structure has finite duality if and only if it has a retract whose square dismantles to its diagonal. ✷

Proof Proof of Theorem 12: Let A be a σ-structure with finite duality. Without loss of generality, we assume that A is a core, so that A has no proper retracts; thus the square of A dismantles to its diagonal. Let (x 1 , y 1 ), . . . , (x k , y k ) be a dismantling sequence of A × A on ∆ A×A . Then Ψ(A × A) ∼ = ΨA × ΨA; we want to prove that it dismantles to ∆ ΨA×ΨA ∼ = Ψ∆ A×A . For i ∈ {1, . . . , k}, define X i to be the substructure of A × A induced by the set

∆ A×A ∪ {(x i , y i ), . . . , (x k , y k )},
and let X k+1 = ∆ A×A . We will show that ΨX i can be dismantled to ΨX i+1 , i = 1, . . . , k. Let b = (b 1 , b 2 ) be an element dominating a = (x i , y i ) in X i . Let f ∈ ΨX i \ ΨX i+1 , and assume that f = (f 1 , f 2 ) : P → A × A. Then there exists (at least one) p 0 ∈ P such that f (p 0 ) = a. We define g = (g 1 , g 2 ) : P → A × A by g(p 0 ) = b and g(p) = f (p) if p = p 0 . Since b dominates a, g is a homomorphism, and obviously g ∈ ΨX i . We claim that g dominates f . Indeed, for R ∈ τ and (f 1 , . . . , f a(R) ) ∈ R(ΨX i ) such that f = f j , there exists a homomorphism h

: Q R → X i such that f = h • q R,j . Define h ′ : Q R → X i by h ′ (q R,j (p 0 )) = b and h ′ (z) = h(z) for z = q R,
j (p 0 ). Since b dominates a = h(q R,j (p 0 )), the mapping h ′ is a homomorphism. By hypothesis, for ℓ = j, the image q R,ℓ (P ) is disjoint from q R,j (P ), whence f ℓ = h ′ • q R,ℓ , while h ′ • q R,j = g. Therefore R(ΨX i ) contains all the a(R)-tuples needed to establish the domination of f by g.

Let p 1 , p 2 , . . . , p m be an enumeration of the elements of P . We dismantle ΨX i to ΨX i+1 by successively removing the functions f such that f (p j ) = (x i , y i ) for j = 1, . . . , m. Proceeding in this way for i = 1, . . . , k, we get a dismantling of ΨA × ΨA ∼ = ΨX 1 to ΨX k+1 ∼ = ∆ ΨA×ΨA . Therefore ΨA has finite duality. ✷

Perhaps the lack of knowledge of a general construction is natural since there is no restriction on the pattern {P } ∪ {(Q R , q R,1 , . . . , q R,a(R) ) : R ∈ τ }. On the other hand, there are many possible transformations T ′ on a family T of tree obstructions, in the style of Sproink(T ). Any such transformation gives rise to a complete set of obstructions to homomorphisms into a structure H ′ = Π T ∈T ′ D T ; however in general there is no way of guaranteeing that such structure H ′ is finite, even when T is a complete set of obstructions for a finite structure H.

Concluding comments

In this paper we tried to shed more light on the structure of tractable templates with tree duality. Let us turn our attention one more time to Fig. 1. The grey areas in the diagram are areas that need a closer look in future research.

Currently we do not know any digraph with a near-unanimity function and with bounded-height tree duality that could not be generated using right adjoints and products, starting from digraphs with finite duality; it is not clear whether any such "reasonable" class of structures with tree duality can be generated from structures with finite duality with a "reasonable" set of adjoint functors.

We have shown here that possession of bounded-height tree duality is decidable. It is natural to ask what its complexity is; in particular, whether it is complete for some class of problems.

Equally interesting is the decidability of membership in other classes depicted in Fig. 1. Tree duality is known to be decidable [START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory[END_REF], but not known to be in PSPACE. Our decision procedure for bounded-height duality is in PSPACE for graphs with tree duality; this suggests that checking tree duality may be harder than checking bounded height of the obstructions.

Furthermore, finite duality is NP-complete [START_REF] Larose | A characterisation of first-order constraint satisfaction problems[END_REF]. The decidability of bounded-treewidth duality is unknown (i) , and so is the decidability of a near-unanimity function (see [START_REF] Maróti | The existence of a near-unanimity term in a finite algebra is decidable[END_REF] for a related result).

The properties of near-unanimity functions proved in the proof of Proposition 5, (i) in the context of digraphs and the arc-graph construction, also hold in the context of general structures and right adjoints. The proofs carry over naturally. (i) Added in Proof: The decidability of bounded-treewidth duality has recently been proved in L. Barto, M. Kozik, Constraint Satisfaction Problems of Bounded Width, preprint, 2009, 18 pages ms.

Figure 1 :

 1 Figure 1: The structure of tractable templates

Figure 2 :

 2 Figure 2: A thunderbolt

  Let f : G → δH be a homomorphism. Then there exist two homomorphisms o, t :

	Proposition 1 For any digraphs G and H,
	G → δH	if and only if	δ -1 G → H.
	Proof:

* Supported by grants from the Natural Sciences and Engineering Research Council of Canada and the Academic Research Program. 1365-8050

It was shown by Pultr [17] that functors Ψ defined by means of patterns are right adjoints into a category of relational structures characterised by axioms of a specific type. We exhibit their corresponding left adjoints Ψ -1 in the case when both the domain and the range of Ψ is the category of all relational structures with a given vocabulary.

For every τ -structure B, we define a σ-structure Ψ -1 B = A/∼, where

• A is a disjoint union of σ-structures; for every element x of the universe of B, A contains a copy P x of P , and for every R ∈ τ and (x 1 , . . . , x r ) ∈ R(B), A contains a copy Q R,(x1,...,xr) of Q R .

• ∼ is the least equivalence which identifies every element u of P xi with its image q R,i (u) in Q R,(x1,...,xr) , for every R ∈ τ , every (x 1 , . . . , x r ) ∈ R(B) and every i ∈ {1, . . . , r}.

Proposition 8 ([17]

) For any τ -structure B and σ-structure A,

Proof: Let h : B → ΨA be a homomorphism, and put h(b) = f b : P → A. Then for every b ∈ B, the mapping f b corresponds to a well-defined homomorphism to A from a copy P b of P . Also, for every R ∈ τ and (b 1 , . . . , b r ) ∈ R(B), we have (h(b 1 ), . . . , h(b r )) ∈ R(ΨA), so there exists a homomorphism g (b1,...,br) : Q R → A such that f bi = g (b1,...,br) • q R,i for i = 1, . . . , r; the mapping g (b1,...,br) corresponds to a well-defined homomorphism from a copy Q R,(b1,...,br) of Q R to A. Therefore b∈B f b ∪ τ R(B) g (b1,...,br) corresponds to a well-defined homomorphism ĥ :

,...,br) → A, such that if x ∼ y, then ĥ(x) = ĥ(y). Therefore ĥ induces a homomorphism from the quotient structure Ψ -1 B to A.

Conversely, if h : Ψ -1 B → A is a homomorphism, we define a homomorphism ĥ : B → ΨA by ĥ(b) = f b , where f b corresponds to the restriction of h to the quotient of P b in Ψ -1 B. Indeed, if R ∈ τ and (b 1 , . . . , b r ) ∈ R(B), then the restriction of h to the quotient of Q R,(b1,...br) in Ψ -1 B corresponds to a homomorphism g : Q R → A such that f bi = g • q R,i for i = 1, . . . , r, whence ( ĥ(b 1 ), . . . , ĥ(b r )) ∈ R(ΨA). ✷

Corollary 9 If a σ-structure A has polynomial CSP, then the τ -structure ΨA also has polynomial CSP. ✷

In fact, Corollary 4 generalises as follows.

Theorem 10 If a σ-structure A has tree duality, then the τ -structure ΨA also has tree duality.

We prove Theorem 10 using Feder and Vardi's characterisation of structures with tree duality. For a σ-structure A, let UA be the σ-structure defined as follows. The universe of UA is the set of all nonempty subsets of A, and for R ∈ σ of arity r, R(UA) is the set of all r-tuples (X 1 , . . . , X r ) such that for all j ∈ {1, . . . , r} and x j ∈ X j there exist x k ∈ X k , k ∈ {1, . . . , r} \ {j} such that (x 1 , . . . , x r ) ∈ R(A).

Theorem 11 ([3])

A structure A has tree duality if and only if there exists a homomorphism from UA to A. ✷