Alessandra Cherubini
email: alessandra.cherubini@polimi.it

Achille Frigeri
email: achille.frigeri@polimi.it

Zuhua Liu
email: liuzuhua@hotmail.com

Composing short 3-compressing words on a 2-letter alphabet *

Keywords: deterministic finite automaton, collapsing word, synchronizing word

A finite deterministic (semi)automaton A = (Q, Σ, δ) is k-compressible if there is some word w ∈ Σ + such that the image of its state set Q under the natural action of w is reduced by at least k states. Such word w, if it exists, is called a k-compressing word for A and A is said to be k-compressed by w. A word is k-collapsing if it is k-compressing for each k-compressible automaton, and it is k-synchronizing if it is k-compressing for all k-compressible automata with k + 1 states. We compute a set W of short words such that each 3-compressible automaton on a two-letter alphabet is 3-compressed at least by a word in W . Then we construct a shortest common superstring of the words in W and, with a further refinement, we obtain a 3-collapsing word of length 53. Moreover, as previously announced, we show that the shortest 3-synchronizing word is not 3-collapsing, illustrating the new bounds 34 ≤ c(3, 2) ≤ 53 for the length c(3, 2) of the shortest 3-collapsing word on a two-letter alphabet.

Introduction

Let A = (Q, Σ, δ) be a finite deterministic complete (semi)automaton with state set Q, input alphabet Σ, and transition function δ : Q × Σ → Q. For any word w ∈ Σ + , the deficiency of w is the difference between the cardinality of Q and the cardinality of the image of Q under the natural action of w. For a fixed k ≥ 1, the word w is called k-compressing for A if its deficiency is greater than or equal to k. An automaton A is k-compressible, if there exists a k-compressing word w for A and in such case A is said to be k-compressed by w. A word w ∈ Σ + is k-collapsing, if it is k-compressing for every k-compressible automaton with input alphabet Σ. A word w ∈ Σ + is called k-synchronizing if it is k-compressing for all k-compressible automata with k + 1 states and input alphabet Σ. Obviously each k-collapsing word is also k-synchronizing.

The concept of k-collapsing words arose (under a different name) in the beginning of the 1990s with original motivations coming from combinatorics [START_REF] Sauer | Composing functions to reduce image size[END_REF]) and from abstract algebra [START_REF] Pöschel | Identities in full transformation semigroups[END_REF]). In [START_REF] Sauer | Composing functions to reduce image size[END_REF] it has been proved that k-collapsing words always exist, for any Σ and any k ≥ 1, by means of a recursive construction which gives a k-collapsing word whose length is O(2 2 k ). Better bounds for c(k, t) and s(k, t), the length of the shortest k-collapsing and k-synchronizing words respectively, on an alphabet of cardinality t were given in [START_REF] Margolis | Words guaranteeing minimum image[END_REF]. The bounds for c (2, t) were slightly improved in [START_REF] Pribavkina | On some properties of the language of 2-collapsing words[END_REF] and [START_REF] Cherubini | A bound for the length of shortest 2 collapsing words[END_REF], but the gaps between lower and upper bounds are quite large even for small values of k and t. Exact values of s(k, t) and c(k, t) are known for k = 2 and t = 2, 3 and are quite far from the theoretical upper bounds [START_REF] Ananichev | Collapsing words: A progress report[END_REF]). Moreover it is known that s(3, 2) = 33 and that the words s 3,2 = ab 2 aba 3 b 2 a 2 babab 2 a 2 b 3 aba 2 ba 2 b 2 a and its dual s3,2 are the unique shortest 3-synchronizing words on {a, b} [START_REF] Ananichev | Quest for short synchronizing words and short collapsing words[END_REF]). Observing that s(k, t) ≤ c(k, t), and applying the construction in [START_REF] Margolis | Words guaranteeing minimum image[END_REF], one gets 33 ≤ c(3, 2) ≤ 154.

The reader is referred to [START_REF] Ananichev | Collapsing words: A progress report[END_REF]; [START_REF] Cherubini | Synchronizing and collapsing words[END_REF]; [START_REF] Cherubini | A bound for the length of shortest 2 collapsing words[END_REF]; [START_REF] Margolis | Words guaranteeing minimum image[END_REF] for references and connections to theoretical computer science and language theory. The paper is organized as follows: in Section 2 we introduce some general concepts about 3-compressible automata and the main tool we use to study them, i.e., 3-Missing State Automata. In Section 3 we give a complete characterization of proper 3-compressible automata on a two-letter alphabet with a letter acting as a permutation, while in Section 4 we characterize all proper 3-compressible automata without permutations. In Section 5 we describe how to use the previous characterization to obtain a short 3collapsing word, improving the known upper bound for c (3,2), as already announced in [START_REF] Cherubini | Short 3-collapsing words over a 2-letter alphabet. In Developments in Language Theory[END_REF]. Section 6 ends the paper with some considerations about the quest for short 3-collapsing words in general and the relationship between 3-synchronizing and 3-collapsing words, and how our analysis can be exploited to obtain more general results, as already done in [START_REF] Cherubini | Synchronizing and collapsing words[END_REF]Kisielewicz (2014, 2016).

Background

Let A = (Q, Σ, δ) be a finite deterministic complete (semi)automaton with state set Q, input alphabet Σ = {a, b}, and transition function δ : Q × Σ → Q. The action of Σ on Q given by δ extends naturally, by composition, to the action of any word w ∈ Σ + on q ∈ Q; we denote it by qw = δ(q, w), while the action of w on the entire state set Q is denoted by Qw = {qw|q ∈ Q}.

Definition 1 The difference |Q| -|Qw| is called the deficiency of the word w with respect to A and denoted by 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 kcollapsing, if it is k-compressing for every k-compressible automaton with input alphabet Σ. A word w is called k-synchronizing if it is k-compressing for all k-compressible automata with k + 1 states and input alphabet Σ. Obviously each k-collapsing word is also k-synchronizing.

Actually, we view the automaton A as a set of transformations on Q induced via δ and labeled by letters of Σ, rather than as a standard triple. Indeed, in order to define an automaton, it is just enough to assign to every letter a ∈ Σ the corresponding transformation τ a : q → δ(q, a) on Q. Now, for a ∈ Σ, we get df A (a) = |Q| -| Im(τ a )|, hence df A (a) = 0 if and only if τ a is a permutation on Q. If df A (a) = m ≥ 1, then there are exactly m different states y 1 , y 2 , . . . , y m / ∈ Im(a), and there are some elements of Q whose images under τ a are equal.

Definition 2 Let P = {{x 1 1 , . . . , x 1 j }, . . . , {x r 1 , . . . , x r j }} be a partition of Q (where singleton sets are omitted), and y 1 , . . . , y m ∈ Q. We say that τ a is a transformation of type [x 1 1 , . . . , x 1 j ] . . . [x r 1 , . . . , x r j ]\y 1 , . . . , y m if P is induced by the kernel of τ a and the states y 1 , y 2 , . . . , y m do not belong to Im(τ a ).

For instance, if A has at least three states denoted by 1, 2 and 3, a transformation τ is of type [1,2]\3, if and only if τ (1) = τ (2), the preimage of 3 is empty, and for any q, q ′ / ∈ {1, 2}, τ (q) = τ (q ′ ) if and only if q = q ′ . So, with an abuse of notation, we will write τ = [1, 2]\3 (actually [1, 2]\3 is a family of transformations). Then, in the sequel we will identify each letter of the input alphabet with its corresponding transformation.

Definition 3 Let a ∈ Σ, we say that a is a permutation letter if it induces a permutation on the set of states, i.e., it has deficiency 0.

We assume that permutations on Q, viewed as elements of the symmetric group S n with |Q| = n, are written in the factorization in disjoint cycles where sometimes also cycles of length 1 are explicitly written. So we will write a = (1)(23)π to denote that (the permutation induced by) a fixes state 1, swaps states 2 and 3, and π is a permutation that acts on Q \ {1, 2, 3} (π is not necessarily a cycle).

The notion of transformation induced by a letter naturally extends to words, and then the semigroup generated by the transformations of A consists precisely of the transformations corresponding to words in Σ + . If A is k-compressible, at least one letter of its input alphabet has deficiency greater than 0. It is well known that each k-collapsing word over a fixed alphabet Σ is k-full [START_REF] Sauer | Composing functions to reduce image size[END_REF]), i.e., contains each word of length k on the alphabet Σ among its factors. Hence, to characterize k-collapsing words it is enough to consider k-full words compressing all k-compressible automata that are proper, i.e., k-compressible automata which are not compressed by any word of length k.

Proposition 4 Let A be a finite complete automaton on the alphabet {a, b}: it is 3-compressible and not proper if at least one letter, say a, fulfills one of the following conditions:

1. it has deficiency greater than 2;

2. it has deficiency 2 and is of type [x, y, z]\u, v, with {u, v} {x, y, z};

3. it has deficiency 2 and is of type [x, y][z, v] The proof of the previous proposition is trivial, indeed if the letter a fulfills one of the above conditions, then either a or a 2 or a 3 has deficiency 3. Since we are looking for a proper 3-compressible automaton we may assume that each letter of the alphabet is either a permutation or one of the following types (we assume different letters represent different states):

1. [x, y, z]\x, y; 2. [x, y][z, v]\x, z; 3. [x, y]\x; 4. [x, y]\z with za = x.
In the sequel we view the set Q of the states of A as a set of natural numbers: Q = {1, 2, . . . , n}, so that, when no confusion arises, a letter a of types 1, 2, 3, 4 is denoted respectively by [1,2,3]\1,2,[1,2][3,4]\1,3,[1,2]\1,[1,2]\3 with 3a = 1.

Definition 5 Let w ∈ Σ + . We call M(w) = Q \ Qw the missing set of w. Let Q 1 ⊆ Q. We denote by M(Q 1 , w) the missing set of w when we have already missed Q 1 , i.e., the set M(w) ∪ {qw | q ∈ Q 1 and ∀q ′ ∈ Q \ Q 1 , qw = q ′ w}. Observe that M(∅, w) = M(w), and if a ∈ Σ is a permutation, M(Q 1 , a) = Q 1 a. Moreover, |M(w)| ≥ |M(w 1 )|, whenever w 1 is a factor of w.
Definition 6 With abuse of language, for a letter a and

Q 1 ⊆ Q, we call the orbit of a over Q 1 the set Orb a (Q 1 ) = ∞ n=0 Q 1 a n .
In order to increase the readability, we will write Orb a (q 1 , . . . , q n ) instead of Orb a ({q 1 , . . . , q n }).

We say that A is a (i, j)-automaton, 1 ≤ i, j ≤ 4, if it is an automaton on a two-letter alphabet {a, b} and the letter a is of type i and b is of type j. We say that A is a (i, p)-automaton, with 1 ≤ i ≤ 4, to denote that the letter a is of type i and b is a permutation. In the sequel, without loss of generality, we will always suppose that in a (i, j)-automaton (resp. (i, p)-automaton) the letter a is of type i and b is of type j (resp. a permutation).

Although the notion of missing set is sufficient to describe the compressibility of an automaton, it is in general quite intricate to use, especially when long words are involved. So, to easily calculate the set M(Q 1 , w), we introduce a graphical device, the missing state automaton of A.

Definition 7 Let A = (Q, Σ, δ) be a deterministic (semi)automaton with |Q| = n, and let m < n. The m-Missing State Automaton (mMSA for short) of A is the automaton M = (℘ m-1 (Q) ∪ {m}, Σ, τ, ∅, m), where ℘ m-1 (Q) is the set of subsets of Q of cardinality less than or equal to m -1, m is a special state not belonging to ℘ m-1 (Q) graphically denoted by a circle with m tokens inside, and τ :

℘ m-1 (Q)×Σ → ℘ m-1 (Q) ∪ {m} is the transition relation defined by τ (Q 1 , a) = M(Q 1 , a), if |M(Q 1 , a)| < m; m, otherwise.
notice that τ is not defined at the state m.

For example, in Fig. 1 we draw the 2MSA of a simple semiautomaton, proving that it is synchronizable. The notion of missing state automaton is similar to that of power state automaton, which is a standard tool in computing synchronizing words, see [START_REF] Trahtman | An efficient algorithm finds noticeable trends and examples concerning the Černý conjecture[END_REF]; [START_REF] Kudlacik | Effective synchronizing algorithms[END_REF][START_REF] Volkov | Synchronizing automata and the Černý conjecture[END_REF]. The difference is that the names of states are replaced by their complements and all superstates made by more than m states are identified. Although power set automata are only used to design algorithm to find possibly shortest synchronizing words of a fixed automaton, we need to consider a whole class of automata. Moreover, as we are only interested in knowing if an automaton is 3-compressible, often we will draw only a Partial 3-Missing State Automaton (P3MSA), i.e., a path (possibly the shortest) from the initial to the final state of the whole 3MSA. Lastly, we observe that when considering a family of automata, dozens of subcases arise when we try to find some (short) 3-collapsing word for such family. So, to capture a greater number of cases and improve the readability, we gather several subcases using a conditional 3MSA. In this case, a label can be of the form a|qw ∈ Q ′ . So, τ (q 1 , a|qw ∈ Q ′ ) = q 2 means that M({q 1 }, a) = {q 2 } under the hypothesis (condition) that qw ∈ Q ′ . Observe that the condition qw ∈ Q ′ spreads over all the states reached from q 2 , so two different states can share the same name, when belonging to different branches. For example, in the conditional 3MSA in Fig. 4(1), the two states named by {1, 3} have different behavior as the one in the first row inherits the condition 3a = 3 and then M({1, 3}, a) = {1, 3}, while the one in the second row inherits the condition 3a = 2 and then M({1, 3}, a) = {1, 2}.

3-compressible (i, p)-automata

In this section we characterize all proper 3-compressible automata on the alphabet {a, b} in which the letter b acts as a permutation on the set Q of states. In particular in the following propositions we give a small set of short 3-collapsing words when letter a is of type i, 1 ≤ i ≤ 4.

Proposition 8 Let A be a (1, p)-automaton with a = [1, 2, 3]\1, 2. Then A is 3-compressible and proper if and only if the following conditions hold:

1. Orb b (1, 2) {1, 2, 3}, and 2. {1, 2}b ⊂ {1, 2, 3}.

Moreover, if A is 3-compressible and proper, then the word ab 2 a 3-compresses A.

Proof: Let A be a (1, p)-automaton that does not satisfy one of the conditions 1. or 2. If Orb b (1, 2) ⊆ {1, 2, 3}, then for each word w ∈ {a, b} * we have that M(wa) = {1, 2}, whence A is not 3-compressible. Else, if {1, 2}b {1, 2, 3}, then M(a) = {1, 2}, M(ab) = {1b, 2b} {1, 2, 3}, and |M(aba)| ≥ 3, so A is not proper.

Conversely, let A be an automaton satisfying conditions 1. and 2. A 3-compressing word for A must have at least two non-consecutive occurrences of letter a, and the word aba is not 3-compressing. Moreover, {1, 2}b 2 {1, 2, 3}, else Orb b (1, 2) ⊆ {1, 2, 3}, against the hypothesis, and then the word ab 2 a 3-compresses A.

2

Proposition 9 Let A be a (2, p)-automaton with a = [1, 2][3, 4]\1, 3. Then A is 3-compressible and proper if and only if one of the following conditions holds:

1. {1, 3}b = {2, 4} and {2, 4}b = {1, 3};

2. {1, 3}b ∈ {{1, 4}, {2, 3}} and at least one of the following conditions is true:

(a) Orb b (1, 3) {1, 2, 3, 4}; (b) |Orb b (1)| = 3; (c) |Orb b (3)| = 3.
Moreover, if A is 3-compressible and proper, then one of the words ab 2 a or ab 3 a 3-compresses A.

Proof: Let A be a (2, p)-automaton that does not satisfy both conditions 1. and 2. If {1, 3}b {1, 2, 3, 4}, then the word aba 3-compresses A, which is not proper. So, let {1, 3}b ⊆ {1, 2, 3, 4}, then we have to consider only the following cases:

1. {1, 3}b ∈ {{1, 2}, {3, 4}}, then again the word aba 3-compresses A, so A is not proper;

2. {1, 3}b = {1, 3}, then for all w ∈ b * , M(w) = ∅, while for all w ∈ {a, b} * \ b * , M(w) = {1, 3}, then A is not 3-compressible; and is of the form (34x)π for some x ∈ {1, 3, 4}. In any cases, {1, 3}b 2 ∈ {{1, x}, {3, 4}}, so the word ab 2 a 3-compresses A. The case {1, 3}b = {2, 3} is symmetric, and then either the word ab 2 a or ab 3 a 3-compresses A.

2

Observe that each 3-compressible (3, p)-or (4, p)-automaton A is proper. Indeed each 3-compressing word for A contains at least three occurrences of the letter a which are not all consecutive. So in the next two propositions, we only look for 3-compressible automata.

Proposition 10 Let A be a (3, p)-automaton with a = [1, 2]\1. Then A is 3-compressible (and proper) if and only if the following conditions hold:

1. |Orb b (1)| ≥ 2 and {1, 2}b = {1, 2}; 2. if b = (13)π, then (a) 3a = 3; (b) if 3a = 2, then 2b = 2 or 2a = 3; (c) if 3a = 2b and 2b ∈ {2, 3}, then 2b 2 = 2 or 2ba = 3; 3. if b = (123)π, or b = (132)π, then {2, 3}a = {2, 3}; 4. if b = (1324)π, then {3, 4}a = {3, 4}.
Moreover, if A is 3-compressible (and proper), then one of the words ababa, aba 2 ba, ab 2 ab 2 a, ab 2 a 2 b 2 a, ab 2 abab 2 a, abab 2 aba, ab 3 aba, abab 3 a or ab 3 ab 3 a 3-compresses A.

Proof: Let A be a (3, p)-automaton that does not satisfy one of the conditions 1.-4. We prove that it is not 3-compressible. Conversely, let A be an automaton satisfying conditions 1.-4. Since |Orb b (1)| ≥ 2 and {1, 2}b = {1, 2}, we have 1b = 1 and b is not of the form (12)π. Moreover, observe that if b is of the form (134 . . .)π, then one of the words abab 2 a, ababa, ab 2 ab 2 a or ab 2 aba 3-compresses A, as shown in Fig. 6. for this reason in the following we do not consider such cases. 24)π, then {2b, 3}a = {2b, 3} and in Fig. 7(1) we draw a P3MSA for those cases, proving that either the word ababa or aba 2 ba 3-compresses A.

(b) If |Orb b (2)| ≥ 3, i.e
., b = (13)(245 . . .)π, then in Fig. 7(2) we draw a P3MSA for this case, proving that either the word ababa or abab 3 a 3-compresses A. 1345)π were already analyzed in Fig. 6.

1 3 1, 3a 1, 3a 2
1 2 3 1, 3a 1, 2a 2, 2ab 3, 2ab 2 2, 3ab 3, 3ab 2 1, 2 1, 2a 2, 2ab 3, 2ab 2 a b b a a|3a = 2 b|3a = 3 b|3a ∈ {2, 3} b b a b a a b b a
Fig. 8: P3MSA for 3-compressible automata with b = (123)π and {2, 3}a = {2, 3}. (a) If b = (1234)π, then in Fig. 10 we draw a P3MSA for this case, proving that one of the words ab 2 ab 2 a, ab 3 ab 3 a, ab 2 abab 2 a or ab 2 a 2 b 2 a 3-compresses A. Indeed, observe that: (a) If b = (12345 . . .)π, then in Fig. 12 we draw a P3MSA for this case, proving that one of the words ab 2 ab 2 a, ab

1 3 1, 3a 1, 2a 3, 2ab 3, 3ab 2, 3 1, 2 1, 2a 3, 2ab a b a a|3a = 2 b|3a = 3 b|3a ∈ {2, 3}
i. if 3a ∈ {3, 4}, then 3ab 2 = 1 implies 3a = 3,
2 abab 2 a or ab 2 a 2 b 2 a 3-compresses A. Note that if 3ab 2 = 1 and 3a 2 b 2 = 2, then 3abab 2 ∈ {1, 2}. In fact if 3abab 2 = 1, then 3a = 3aba, hence 3a = 2 and 3ab 2 = 4, a contradiction. If 3abab 2 = 2, then 3aba = 3a 2 , hence 3ab = 3a and 3ab 2 = 3ab = 1, again a contradiction. Similarly, if 3ab 2 = 2 and 4ab 3 = 2, then 3abab 2 ∈ {1, 2}; in fact if 3abab 2 = 1 then 3ab 2 ab 2 = 4ab 2 and 3ab 2 = 4, else if 3abab 2 = 2 then 3ab 2 = 3abab 2
hence 3ab = 3 and 3ab 2 = 4, and in both cases this is a contradiction. (b) If b = (13245 . . .)π, then in Fig. 13 we draw a P3MSA for this case, proving that one of the words ab 3 ab 3 a, ab 3 aba or abab 3 a or ababa 3-compresses A. 2

1 2 3 1, 3a 2, 3ab 3, 3ab 2 4 1, 4 1, 2 2, 3 3, 4 1, 3 2, 4 1, 4a 2, 4ab 3, 4ab 2 1, 4 1, 4a 2, 4ab 3, 4ab 2 1, 4 1, 2 1, 2a 2, 2ab 3, 2ab 2 a b b a|3a ∈ {3, 4} b|3a
2 3 1, 3a 2, 3ab 3, 3ab 2 1, 3a 2 2, 3a 2 b 3, 3a 2 b 2 2, 3ab 1, 3aba 2, 3abab 3, 3abab 2 a b b a b|3ab 2 ∈ {1, 2} b a a|3ab 2 ∈ {1, 2}, 3a 2 b 2 ∈ {1, 2} b b a b|{3ab 2 , 3a 2 b 2 } = {1, 2}
Proposition 11 Let A be a (4, p)-automaton with a = [1, 2]\3, 3a = 1. Then A is 3-compressible (and proper) if and only if the following conditions hold:

1. {1, 3}b = {1, 3}; 2. b = (12)(3)π; 3. if b = (1)(23)π, or b = (123)π, or b = (132)π, then 2a = 2; 4. if b = (1)(2)(34)π, or b = (12)(34)π, or b = (14)(23)π, or b = (1423)π, or b = (1324)π, then 4a = 2.
Moreover, if A is 3-compressible (and proper), then one of the words a 2 ba 2 , a 2 b 2 a 2 , a 2 b 3 a, a 2 baba 2 or ab 3 ab 3 a 3-compresses A.

Proof: Let A be a (4, p)-automaton that does not satisfy one of the conditions 1.-4. We prove that it is not 3-compressible.

1. Let condition 1. be false, i.e., {1, 3}b = {1, 3}, then the 3MSA in Fig. 14(1) proves that A is not 3-compressible.

2. Let condition 2. be false, i.e., b = (12)(3)π, then the 3MSA in Fig. 14(2) proves that A is not 3-compressible. (1) 3MSA for the case {1, 3}b = {1, 3}. Fig. 14: 3MSA for automata that do not satisfy conditions 1. or 2. of Proposition 11.

(b) if b = (124 . . .)(3)π, then M(a 2 b) = {2, 3}, M(a 2 b 2 ) = {3, 4}, M(a 2 b 2 a) = {1, 3, 4a},
and the word a 2 b 2 a 3-compresses A.

= (145 . . .)(23)π, then M(a 2 b) = {2, 4}, M(a 2 b 2 ) = {3, 5}, M(a 2 b 2 a) = {1, 3, 5a},
and the word a 2 b 2 a 3-compresses A. (a) 3b = 1.

i. If b = (3124 . . .)π, then M(a 2 b) = {1, 2}, M(a 2 b 2 ) = {2, 4}, M(a 2 b 3 ) = {4, 4b}, M(a 2 b 3 a) = {3, 4a, 4ba}
and the word a 2 b 3 a 3-compresses A.

ii. If b = (314 . . .)π, then the P3MSA in Fig. 18 proves that one of the words a 2 baba 2 , a 2 b 2 a or ab 2 a 2 3-compresses A. Observe that if 4a = 2 and 4b = 2, then b is of the form (31425 . . .)π, otherwise condition 4. is not satisfied. (b) 3b = 2.

i. If b = (3214 . . .)π, then the P3MSA in Fig. 19 proves that either the word a 2 ba 2 or ab 3 ab 3 a 3-compresses A. In this section we characterize proper 3-compressible automata on 2-letter alphabet where no letter acts as a permutation.

Proposition 12 Let A a (i, j)-automaton with i ∈ {1, 2} and j ∈ {1, 2, 4}, then A is either not 3compressible or not proper.

Proof: We have to consider five different cases. (c) if {x, z} = {1, 3}. If x = 1 and z = 3, the P3MSA in Fig. 21(1) proves that if 2b = y = 2 then A is not 3-compressible, else it is not proper. If x = 3 and z = 31, the P3MSA in Fig. 21(2) proves that if y = 2 then A is not 3-compressible, else it is not proper; (d) if {x, z} = {2, 3}, this case reduces to the previous exchanging the state 1 and 2. , then for all w ∈ {a, b} + , we have M(wa) = {1, 3} and M(wb) = {1, 4}, so A is not 3-compressible; ii. if x = 1 and z = 4, then if y = 2 the P3MSA in Fig. 22(1) proves that A is not proper. Else, if y = 2 and 3b = 2, then the word aba 3-compresses A which is not proper. Otherwise, if y = 2 and 3b = 2, then the 3MSA in Fig. 22 proves that A is not 3-compressible;

1, 2 3, 2b z 1, 3 1, 2 2
(e) if {x, z} = {2, 3}, this case reduces to the previous exchanging the state 1 and 3, as well as the states 2 and 4; 3]\2 and q = 1 then, if qb = y we have M(ab) = {z, qb} and M(aba) = {1, 3, qba}, so the automaton is not proper, else if qb = y A is not 3-compressible, as shown in Fig. 22(2);

(f) if {x, z} = {2, 4} and {x, y} ∩ {1, 3} = ∅ then y ∈ {1, 3}. Let q ∈ {1, 3} \ {y}: i. if b = [2, 1]\4 and q = 3, or b = [4,
ii. if b = [2,3]\4 and q = 1, or b = [4, 1]\2 and q = 3 then either the word ab 2 or aba 3-compresses A, so it is not proper. 1. x ∈ {1, 2, 3};

2. {1, 2} ∩ {x, y} = ∅; 3. if x ∈ {1, 2}, then for q ∈ {1, 2} \ {x} it is qb ∈ {1, 2, 3} and Orb b (q) ⊆ {1, 2,
4. if x = 3, then for q ∈ {1, 2} \ {y} it is qb ∈ {1, 2, 3} and Orb b (q) ⊆ {1, 2, 3}.

Moreover, if A is 3-compressible and proper, then the word ab 2 a 3-compresses A.

Proof: Let A be a (1, 3)-automaton that does not satisfy one of the conditions 1.-3.

1. Let x ∈ {1, 2, 3}, then the word ba 3-compresses A, and so it is not proper.

2. Let {1, 2} ∩ {x, y} = ∅, then the word ab 3-compresses A, and so it is not proper.

3. Now let x ∈ {1, 2, 3} and {1, 2} ∩ {x, y} = ∅.

(a) Suppose x ∈ {1, 2} and let q ∈ {1, 2} \ {x}.

i. If qb ∈ {1, 2, 3}, then M(ab) = {qb, x} and M(aba) = {1, 2, qba}, so the word aba 3-compresses A which is not proper. ii. Suppose qb ∈ {1, 2, 3} and Orb b (q) ⊆ {1, 2, 3}, then qb ∈ {q, 3} and 3b = q, so A is not 3-compressible, as shown in Fig. 23(1).

(b) Lastly, suppose x = 3 and let q ∈ {1, 2} \ {y}.

i. If qb ∈ {1, 2, 3}, then M(ab) = {qb, x} and M(aba) = {1, 2, qba}, so the word aba 3-compresses A which is not proper. ii. Suppose qb ∈ {1, 2, 3} and Orb b (q) ⊆ {1, 2, 3}. Then y ∈ {1, 2} (as {1, 2}∩{x, y} = ∅) and qb ∈ {1, 2} = {q, y} (as x = 3 does not belong to the image of b). Moreover, as Orb b (q) ⊆ {1, 2} = {q, y}, also yb ∈ {1, 2} and then A is not 3-compressible, as shown in Fig. 23(2). (1) 3MSA for the case x ∈ {1, 2}, q ∈ {1, 2} \ {x}, qb ∈ {q, 3} and 3b = q.

1, 2 3, q 1, 2 Moreover, if A is 3-compressible and proper, then either the word ab 2 a or ab 3 a 3-compresses A.

Proof: Let A be a (2, 3)-automaton that does not satisfy one of the conditions 1.-5.

1. Let x ∈ {1, 2, 3, 4}, then the word ba 3-compresses A, and so it is not proper.

Let x = 1:

(a) if 3b = 4, then if 3b = 3 A is not 3-compressible, while if 3b = 3 the word aba 3-compresses A that it is not proper, as shown in Fig. 24(1);

(b) if 3b = 4 and Orb b (3) ⊆ {3, 4}, then A is not 3-compressible, as shown in Fig. 24(2). Fig. 24: 3MSA for automata that do not satisfy condition 2. of Proposition 14.

Let x = 2:

(a) if y ∈ {1, 3}, then the word ab 3-compresses A, and so it is not proper;

(b) if y = 1, then if 3b = 4, then A is not 3-compressible, as shown in Fig. 25(1); while if 3b = 4 and 4b = 3, then A is not 3-compressible, as shown in Fig. 25(2); (c) if y = 3 and 1b ∈ {3, 4}, then M(ab) = {2, 1b}, and M(aba) = {1, 3, 1ba}, so the word aba 3-compresses A that it is not proper.

The cases with x = 3 and x = 4 are symmetrical to case 3. and 4., respectively. Conversely, suppose x ∈ {1, 2, 3, 4}.

1. Let x = 1, 3b = 4 and Orb b (3) ⊆ {3, 4}, this implies 4b = 3b 2 ∈ {3, 4}. Then M(ab) = {1, 4}, M(ab 2 ) = {1, 4b} and M(ab 2 a) = {1, 3, 4ba}, so ab 2 a 3-compresses A.

Let x = 2:

(a) if y = 1, 3b = 4 and 4b = 3, then M(ab) = {2, 4}, M(ab 2 ) = {2, 4b} and M(ab 2 a) = {1, 3, 4ba}, so ab 2 a 3-compresses A;

(b) if y = 3 and 1b ∈ {3, 4}, then either the word ab 2 a or ab 3 a 3-compresses A, as shown in Fig. 26. The cases with x = 3 and x = 4 are symmetrical to those with x = 1 and x = 2, respectively. 2

1, 3 2, 1b 2, 1b 2 2, 1b 3 a b b b|1b 2 ∈ {3, 4} b|1b
The following lemma is straightforward.

Lemma 15 Let A be a 1. {1ba, 1b 2 a, 1b 3 a} ⊆ {2, y}, or 2. Orb a (1ba) ⊆ {2, y}.

Proof: Let A be a (3, 3)-automaton that does not satisfy the above conditions, we prove that it is not 3-compressible.

1. Let 1b = 1 and Orb a (1ba) ⊆ {2, y}.

(a) If 1ba = 1a = 2a = 2, then the 3MSA in Fig. 27(1) proves that A is not 3-compressible.

(b) If 1ba = 1a = 2a = y, then ya = 1ba 2 = 2 and the 3MSA in Fig. 27(2) proves that A is not 3-compressible.

2. Let 1b = 1, {1ba, 1b 2 a, 1b 3 a} ⊆ {2, y} and Orb a (1ba) ⊆ {2, y}. If 1ba = 1b 2 a or 1b 2 a = 1b 3 a, then, since for all h > 0 we have that 1b h = 2, we obtain that 1 = 1b, against the hypothesis. If 1b 2 a = 1b 3 a, as 1b 2 = 2, then 1b 2 = 1b 3 , and then 1 = 1b, against the hypothesis. So, as |{1ba, 1b 2 a, 1b 3 a}| ≤ 2, 1ba = 1b 3 a, then 1b = 1b 3 and 1 = 1b 2 .

(a) If 1ba = 2, then 1b 2 a = y, hence 1a = 2a = y, ya = 2 and 1b = y. The 3MSA in Fig. 28(1) proves that A is not 3-compressible. (2) Case 1a = y.

Fig. 27: 3MSA for automata that do not satisfy conditions 1. and 2. of Lemma 16 with 1b = 1. Proof: Let A be a (3, 3)-automaton that does not satisfy the above conditions, we prove that it is not 3-compressible or not proper. In all the subcases, A is not 3-compressible. Proof: First observe that from the previous corollary a proper 3-compressible (3, 4)-automaton always satisfies the antecedent of one of the above conditions, so all the possible cases are taken into account.

We start proving that a (3, 4)-automaton that does not satisfy the conditions 1.-3. is not 3-compressible.

1. Let condition 1. be false, i.e., b = [x, y]\1 and Orb a (x) ⊆ {x, y}. The 3MSA in Fig. 30 proves that A is not 3-compressible. The 3MSA in Fig. 31(3) proves that A is not 3-compressible. (1) 3MSA for the case b = [1, y]\2, 2b = 1, Orba(2) ⊆ {2, y} and 2ab ∈ {1, y}. 32(1) proves that A is not 3compressible. Else, if x = 2 and y = 1, then the 3MSA in Fig. 32(2) proves that A is not 3-compressible. Proof: First observe that from Corollary 24, a proper 3-compressible (4, 4)-automaton always satisfies the antecedent of one of the above conditions, so all the possible cases are taken into account.

1 1, x 1, x 1, y 1, x a,
2 1 2, x 2, x 1, 2 1, x 1, x 1, 2 2
z 1 1, z 1, za 1, z 1, za 2
We start proving that a (4, 4)-automaton that does not satisfy conditions 1.-4. is not proper or it is not 3-compressible.

1. Let condition 1. be false, i.e., b = [x, y]\1 but either y = 3 or xa = 2 and 2b = 3. Observe that if y = 3 then from the previous corollary we have x = 3. The 3MSA in Fig. 38 proves that if condition 1. is false, then A is not 3-compressible. then the P3MSA in Fig. 42(1) proves that the word a 2 b 2 3-compresses A. If 2a = 2, then the P3MSA in Fig. 42(2) proves that the word a 2 ba 2 3-compresses A. Then, in order to construct a short 3-collasing word, we find a word having as factor all the words above, i.e., we solve the Shortest Common Supersequence problem (SCS) for W . It is well-known that SCS is NP-complete [START_REF] Raiha | The shortest common supersequence problem over binary alphabet in NPcomplete[END_REF]) even on a two-letter alphabet, thus approximation algorithm are often used. Nevertheless, the cost of finding a good approximation is comparable to the cost of finding an optimal solution [START_REF] Karpinski | Improved inapproximability results for the shortest superstring and related problems[END_REF]) and, on the other hand, efficient algorithms give poor approximation [START_REF] Turner | Approximation algorithms for the shortest common superstring problem[END_REF]).

So, as no near-optimal solutions can be found in reasonable time, we decided to code the problem in the bounded satisfiability problem for a set of linear-time temporal logic (LTL) formulae, and to solve it with the tool described in [START_REF] Bersani | Constraint LTL satisfiability checking without automata[END_REF]. More precisely, let S be a propositional letter, a word w of length n is coded in the LTL formula w that is satisfied if and only if for all 1 ≤ i ≤ n the i-th letter of w is "a" if and only if at the i-th time instant S is true. E.g., the word aba is encoded in the formula S ∧ (X(¬S ∧ X(S))), where X is the "next" operator. Then we look for the shortest model that satisfy the formula w∈W w: such model encodes the shortest word having as factor all the words in W and has length 55.

However, we were well aware that such "greedy approach", i.e., to find an optimal solution for each subcase and combining them to obtain a global one, is not suitable in order to achieve a global optimum.

We observed that the words a 2 b 3 a 2 and b 2 a 3 b 2 are needed only to solve a special subcase of (3, 4)automata, so we tried to replace them with a longer factor in order to obtain a shorter 3-collapsing word.

Actually, the shortest word having as a factor the words in W \ {a It is known that in general the language C k,t of k-collapsing words on an alphabet of t letters differs from the language S k,t of k-synchronizing words on the same alphabet. However, this not excludes that in some cases c(k, t) and s(k, t), respectively the length of the shortest k-collapsing and k-synchronizing word on an alphabet of t letters, can be equal. Up to now it was only known that c(2, 2) = s(2, 2) [START_REF] Sauer | Composing functions to reduce image size[END_REF]) and that c(2, 3) = s(2, 3) [START_REF] Ananichev | Quest for short synchronizing words and short collapsing words[END_REF]). We find a counterexample proving that c(3, 2) = s(3, 2) (and so c(3, 2) ≥ 34). In fact, the semiautomaton in Fig. 44(2) is 3compressible (and also 3-synchronizing), but the word s 3,2 do not compresses it. On the other hand, its dual s3,2 synchronizes it.

We believed that any 3-compressible 5-states automaton on a two-letter alphabet were 3-compressed either by s 3,2 or by s3,2 , but an Anonymous reviewer observed that this is not the case: the semiautomaton in Fig. 44 is 3-synchronizable but it is not 3-compressed neither by s 3,2 nor by s3,2 .

Conclusion

Although very technical, our analysis can be effectively exploited in order to obtain more general results and to investigate some conjectures. In [START_REF] Cherubini | Synchronizing and collapsing words[END_REF]Kisielewicz (2014, 2016), the authors exploit the characterization of (3, p)-automata (Proposition 10) to prove that the problem of recognizing whether a binary word is 3-collapsing is co-NP-complete. Moreover, the word w 3 can be used to improve the procedure arising from Margolis et al. ( 2004) (Theorem 3.5) to obtain shorter k-collapsing words for k ≥ 4. In particular, it follows that c(4, 2) ≤ 1741 and c(5, 2) ≤ 109941. Though very lengthy, they can be effectively used in testing the compressibility of an automaton. In particular, this can accelerate the algorithm presented in [START_REF] Ananichev | Quest for short synchronizing words and short collapsing words[END_REF]; [START_REF] Petrov | An algorithm for recognition of n-collapsing words[END_REF] to find short (possibly shortest) 4-and 5-synchronizing words.

Fig. 1 :

 1 Fig.1: The Cerný semiautomaton with 3 states and its 2MSA: the set of synchronizing words for A is the regular language b * a(a + ba + b 3 ) * bba.

3 .

 3 {1, 3}b ∈ {{1, 4}, {2, 3}} with Orb b (1, 3) ⊆ {1, 2, 3, 4}, |Orb b (1)| = 3 and |Orb b (3)| = 3, then b = (1423)π or b = (1324)π or b = (1)(34)π or b = (12)(3)π. The 3MSA in figures 2(1) and 2(2) prove that in any case A is not 3-compressible; 4. {1, 3}b = {2, 4}. If {2, 4}b ⊆ {1, 2, 3, 4}, then b = (12)(34)π or b = (14)(32)π or b = (1234)π or b = (1432)π, and the 3MSA in Fig. 2(2) proves that A is not 3-compressible. 3MSA for the case b = (1423)π or b = (1324)π. for the case b = (1)(34)π, b = (12)(4)π, or {1, 3}b = {2, 4}.

Fig. 2 :

 2 Fig.2: 3MSA for automata that do not satisfy conditions 1. and 2. of Proposition 9.

  1. Let |Orb b (1)| = 1 or {1, 2}b = {1, 2}, then 1b = 1 or b = (12)π. In the former case for all w ∈ (a + b) * , M(w) ∈ {∅, {1}}, in the latter M(w) ∈ {∅, {1}, {2}}, so A is not 3-compressible. 2. Let b = (13)π and either 3a = 3, or 3a = 2, 2b = 2 and 2a = 3, or 3a = 2b = 4, 2b 2 = 2 and 2ba = 3. Observe that in the last two cases 3a 2 = 3 and 3ab = 2, indeed if 3a = 2, 2b = 2 and 2a = 3 then (3a)a = 2a = 3 and (3a)b = 2b = 2, while if 3a = 2b = 4, 2b 2 = 2 and 2ba = 3, then again (3a)a = (2b)a = 3 and (3a)b = (2b)b = 2. The 3MSA in Fig. 3 proves that in any case A is not 3-compressible. 3. Let b = (123)π, or b = (132)π, and {2, 3}a = {2, 3}. The 3MSA in figures 4(1) and 4(2) prove that A is not 3-compressible. 4. Let b = (1324)π, and {3, 4}a = {3, 4}. The 3MSA in Fig. 5 proves that A is not 3-compressible.

Fig. 3 :

 3 Fig.3: 3MSA for automata that do not satisfy condition 2. of Proposition 10.

Fig. 4 :

 4 Fig. 4: 3MSA for automata that do not satisfy condition 3. of Proposition 10.

Fig. 5 :

 5 Fig. 5: 3MSA for automata that do not satisfy condition 4. of Proposition 10.

Fig. 6 :

 6 Fig. 6: P3MSA for 3-compressible automata with b = (134 . . .)π.

( 2 )

 2 for the case b = (13)(2)π or b = (13)(24)π, and {2b, 3}a = {2b, P3MSA for the case b = (13)(245 . . .)π.

Fig. 7 : 3 .

 73 Fig. 7: P3MSA for 3-compressible automata with b = (13)π and 3a = 3.

Fig. 9 :

 9 Fig. 9: P3MSA for 3-compressible automata with b = (132)π and {2, 3}a = {2, 3}.

and 3ab 2 = 2

 22 implies 3a = 4, and both of them are contradictions; ii. if 3a = 4 and 4a = 3, then 2ab 2 = 1 implies 2a = 3, and 2ab 2 = 2 implies 2a = 4, both contradictions; iii. if 3a = 3 and 4a = 4 or if 3a = 4 and 4a = 3, then 4ab 2 = 1 implies 4a = 3, and 4ab 2 = 2 implies 4a = 4, both contradictions. (b) If b = (1324)π, then {3, 4}a = {3, 4} and in Fig. 11 we draw a P3MSA for this case, proving that either the word ababa or ab 3 aba 3-compresses A. Observe that if 3ab = 1, then 3a = 4, 4a = 3, and so 4ab ∈ {1, 2}, else if 3ab = 2, then 3a = 3, 4a ∈ {3, 4}, and again 4ab ∈ {1, 2}. 4. Let |Orb b (1)| ≥ 5, then we have to considered the two subcases b = (12345)π and b = (13245)π, as the cases b = (13425 . . .)π, b = (13452 . . .)π, and b = (13456 . . .)π were already analyzed in Fig. 6.

Fig. 10 :

 10 Fig. 10: P3MSA for the case b = (1234)π.

Fig. 11 :

 11 Fig. 11: P3MSA for the case b = (1324)π and {3, 4}a = {3, 4}.

  1

Fig. 12 :

 12 Fig. 12: P3MSA for the case b = (12345 . . .)π.

Fig. 13 :

 13 Fig. 13: 3MSA for the case b = (13245 . . .)π.

3 .

 3 Let condition 3. be false, i.e., b = (1)(23)π or b = (123)π or b = (132)π, and 2a = 2. Then the 3MSA in figures 15(1), 15(2) and 15(3) prove that A is not 3-compressible. 4. Let condition 4. be false, i.e., b = (1)(2)(34)π or b = (12)(34)π or b = (14)(23)π or b = (1423)π or b = (1324)π, and 4a = 2. Then the 3MSA in figures 16(1), 16(2), 16(3) and 16(4) prove that A is not 3-compressible.

( 2 )

 2 3MSA for the case b = (12)(3)π.

  3MSA for the case b = (1)(23)π and 2a = 2.

  3MSA for the case b = (123)π and 2a = 2.

  3MSA for the case b = (132)π and 2a = 2.

Fig. 15 :

 15 Fig. 15: 3MSA for automata that do not satisfy condition 3. of Proposition 11.

2 .( 3 )

 23 Let Orb b (3) = {2, 3}, then there are two further subcases: (a) if b = (14)(23)π, and 4a = 2, then M(a 2 b) = {2, 4}, M(a 2 ba) = {3, 4a}, M(a 2 ba 2 ) = {1, 3, 4a 2 }, and the word a 2 ba 2 3-compresses A; 3MSA for the case b = (1423)π and 4a = 23MSA for the case b = (1324)π and 4a = 2.

Fig. 16 :

 16 Fig. 16: 3MSA for automata that do not satisfy condition 4. of Proposition 11. (b) if b= (145 . . .)(23)π, then M(a 2 b) = {2, 4}, M(a 2 b 2 ) = {3, 5}, M(a 2 b 2 a) = {1, 3, 5a},and the word a 2 b 2 a 3-compresses A.

3 .

 3 Let Orb b (3) = {3, 4}, i.e., b = (34)π, then in Fig.17we draw a P3MSA for this case, proving that one of the words a 2 b 2 a, a 2 ba, aba 2 or ababa 3-compresses A. Observe that, if 4a = 2 and 1b = 1, then by condition 4. we have 2b = 2. Similarly, if 4a = 2 and 1b = 2, then 2b = 1.

Fig. 17 :

 17 Fig. 17: P3MSA for the case b = (34)π.

Fig. 18 :

 18 Fig. 18: P3MSA for the case b = (314 . . .)π.

Fig. 19 :

 19 Fig. 19: P3MSA for the case b = (3214 . . .)π.

Fig. 20 : 2 4 3 -

 2023 Fig. 20: P3MSA for the case b = (324 . . .)π.

  1. Let A be a (1, 1)-automaton with a = [1, 2, 3]\1, 2 and b = [x, y, z]\x, y:(a) if {1, 2} ⊆ {x, y, z} and {x, y} ⊆ {1, 2, 3}, then for any w ∈ {a, b} * , we have M(wa) = {1, 2} and M(wb) = {x, y}, so A is not 3-compressible; (b) if {1, 2}{x, y, z}, then |M(ab)| ≥ 3, so A is not proper; similarly if {x, y} {1, 2, 3}, then |M(ba)| ≥ 3, and again A is not proper. 2. Let A be a (1, 2)-automaton with a = [1, 2, 3]\1, 2 and b = [x, y][z, v]\x, z: (a) if {1, 2} ∈ {{x, z}, {x, v}, {y, z}, {y, v}} and {x, z} ⊆ {1, 2, 3}, then for any w ∈ {a, b} * , we have M(wa) = {1, 2} and M(wb) = {x, z}, so A is not 3-compressible; (b) if {1, 2} ∈ {{x, z}, {x, v}, {y, z}, {y, v}}, then |M(ab)| ≥ 3, so A is not proper; similarly if {x, z} {1, 2, 3}, then |M(ba)| ≥ 3, and again A is not proper. 3. Let A be a (2, 2)-automaton with a = [1, 2][3, 4]\1, 3 and b = [x, y][z, v]\x, z: (a) if {1, 3} ∈ {{x, z}, {x, v}, {y, z}, {y, v}} and {x, z} ∈ {{1, 3}, {1, 4}, {2, 3}, {2, 4}}, then for all w ∈ {a, b} * , we have M(wa) = {1, 3} and M(wb) = {x, z}, so A is not 3compressible; (b) if {1, 3} ∈ {{x, z}, {x, v}, {y, z}, {y, v}}, then |M(ab)| ≥ 3, so A is not proper; similarly if {x, z} ∈ {{1, 3}, {1, 4}, {2, 3}, {2, 4}}, then |M(ba)| ≥ 3, and again A is not proper.4. Let A be a (1, 4)-automaton with a = [1, 2, 3]\1, 2 and b = [x, y]\z, zb = x: (a) if {x, z} {1, 2, 3}, then M(b 2 ) = {x, z} and M(b 2 a) = {1, 2, xa, za}, so A is not proper; (b) if {x, z} = {1, 2}, then for all w ∈ {a, b} + \ {b}, we have M(w) = {1, 2}, so A is not 3-compressible;

  P3MSA for the case x = 1 and z = 3. for the case x = 3 and z = 1.

Fig. 21 :

 21 Fig. 21: 3MSA for a (1, 4)-automaton with a = [1, 2, 3]\1, 2, b = [x, y]\z, zb = x and {x, z} = {1, 3}.

5 .

 5 Let A be a (2, 4)-automaton with a = [1, 2][3, 4]\1, 3 and b = [x, y]\z, zb = x:(a) if {x, z} ∈ {{1, 3}, {1, 4}, {2, 3}, {2, 4}}, then M(b 2 ) = {x, z} and |M(b 2 a)| ≥ 3, so A is not proper; (b) if {x, y} ∩ {1, 3} = ∅, then M(ab) = {1b, 3b,z}, so A is not proper; (c) if {x, z} = {1, 3}, then for all w ∈ {a, b} + \ {b}, we have M(w) = {1, 3}, so A is not 3-compressible; (d) if {x, z} = {1, 4} and {x, y} ∩ {1, 3} = ∅, we consider two subcases: i. if x = 4 and z = 1, then y must be equal to 3. So b = [4, 3]\1

  for the case b = [1, 2]\4, 4b = 1, 3b = 2, or b = [2, 1]\4, 4b = 1 and 3b = 1, or b = [4, 3]\2, 2b = 4 and 1b = 3.

Fig. 22 :

 22 Fig. 22: 3MSA for a (2, 4)-automaton with a = [1, 2][3, 4]\1, 3 and b satisfying either condition (d).ii or (f).i.

  for the case x = 3, q ∈ {1, 2} \ {x}, y ∈ {1, 2} and {qb, yb} = {q, y} = {1, 2}.

Fig. 23 : 2

 232 Fig. 23: 3MSA for automata that do not satisfy condition 3. or 4. of Proposition 13.

( 2 )

 2 Case Orb b (3) ⊆ {3, 4} and 3b = 4.

( 2 )

 2 Case 3b = 4 and 4b = 3.

Fig. 25 :

 25 Fig. 25: 3MSA for automata that do not satisfy condition 3. of Proposition 14 with y = 1.

Fig. 26 :

 26 Fig. 26: P3MSA for the case b = [2, 3]\2 and 1b ∈ {3, 4}.

( 3 ,

 3 3) 3-compressible automaton with a = [1, 2]\1 and b = [x, y]\x. Then x = 1 and {x, y} = {1, 2}. Lemma 16 Let A be a (3, 3) 3-compressible automaton with a = [1, 2]\1 and b = [2, y]\2 with y = 1. Then:

( 2 )

 2 Case 1ba = y.

Fig. 28 : 2 Corollary 17 2 . 3 .

 2821723 Fig. 28: 3MSA for automata that do not satisfy conditions 1. and 2. of Lemma 16 with 1b = 1. (b) If 1ba = y, then 1b 2 a = 1a = 2a = 2. Moreover, 1ba 2 = y, otherwise 1ba 2 = 2 gives the contradiction 1ba = 1, hence ya = y, 1b = y and yb = 1b 2 = 1. The 3MSA in Fig. 28(2) proves that A is not 3-compressible. 2 Corollary 17 Let A be a (3, 3) 3-compressible automaton with a = [1, 2]\1 and b = [x, 1]\x with x = 2. Then: 1. {xab, xa 2 b, xa 3 b} ⊆ {1, 2}, or 2. Orb b (xab) ⊆ {1, 2}. Proof: It is a straightforward consequence of the previous lemma, simply replacing a with b, 1 with 2, 2 with y and x with 1. 2 Lemma 18 Let A be a proper (3, 3) 3-compressible automaton with a = [1, 2]\1 and b = [x, y]\x with x ∈ {1, 2} and y = 1. Then all the following conditions hold: 1. 1b ∈ {1, 2}; 2. xa ∈ {x, y}; 3. Orb b (1) ⊆ {1, 2} or Orb a (x) ⊆ {x, y}.

1. 3 .

 3 If 1b ∈ {1, 2}, then A is not proper, in fact M(ab) = {x, 1b} and |M(aba)| = 3; similarly 2. if 1b ∈ {1, 2} and xa ∈ {x, y}, then A is not proper, in fact M(ba) = {1, xa} and |M(bab)| = 3. If 1b ∈ {1, 2}, xa ∈ {x, y}, Orb b (1) ⊆ {1, 2} and Orb a (x) ⊆ {x, y}, then (a) if 1b = 1 and xa = x, the 3MSA of A is in Fig. 29(1); (b) if 1b = 1 and xa = y (and then ya = x), the 3MSA of A is in Fig. 29(2); (c) if 1b = 2 (and then 2b = 1) and xa = x, the 3MSA of A is in Fig. 29(3); (d) if 1b = 2 (and then 2b = 1) and xa = y (and then ya = x) the 3MSA of A is in Fig. 29(4). 1b = 2, 2b = 1, xa = y and ya = x.

Fig. 29 :

 29 Fig. 29: 3MSA for automata that do not satisfy conditions 3. of Lemma 18

2 Proposition 19 2 Lemma 20

 219220 Let A be a(3, 3)-automaton with a = [1, 2]\1 and b = [x, y]\x. Then A is 3-compressible and proper if and only if one of the following conditions holds:1. b =[2, y]\2, y = 1, and either {1ba, 1b 2 a, 1b 3 a} ⊆ {2, y} or Orb a (1ba) ⊆ {2, y}; 2. b = [x, 1]\x, x = 2, and either {xba, xb 2 a, xb 3 a} ⊆ {1, 2} or Orb b (xab) ⊆ {1, 2}; 3. b = [x, y]\x, x ∈ {1, 2}, y = 1, 1b ∈ {1, 2}, xa ∈ {x, y}, and either Orb b (1) ⊆ {1, 2} or Orb a (x) ⊆ {x, y}. Moreover, if A is 3-compressible and proper, then one of the words abab or ab 2 ab or ab 3 ab or aba 2 b or aba 3 b or baba or ba 2 ba or ba 3 ba or bab 2 a or bab 3 a 3-compresses A. Proof: If A is a 3-compressible (3, 3)-automaton with a = [1, 2]\1 and b = [x, y]\x, then, from lemmata 15, 16 and 18 and Corollary 17, one of the above conditions must hold. Conversely, we find for any automaton satisfying conditions 1. -3. a (short) 3-compressing word. 1. Let b = [2, y]\2 and y = 1: (a) if {1ba, 1b 2 a, 1b 3 a} ⊆ {2, y}, then either the word abab or ab 2 ab or ab 3 ab 3-compresses A, since M(aba) = {1, 1ba}, M(ab 2 a) = {1, 1b 2 a} and M(ab 3 a) = {1, 1b 3 a}; (b) if Orb a (1ba) ⊆ {2, y}, then {1ba, 1ba 2 , 1ba 3 } ⊆ {2, y} and either the word abab or aba 2 b or aba 3 b 3-compresses A, since M(aba) = {1, 1ba}, M(aba 2 ) = {1, 1ba 2 } and M(ab 3 a) = {1, 1ba 3 }. 2. Let b = [x, 1]\x, x = 2, and either {xba, xb 2 a, xb 3 a} ⊆ {1, 2} or Orb b (xab) ⊆ {1, 2}. This case reduces to the previous one replacing a with b, 1 with 2, 2 with y and x with 1, then either the word baba or ba 2 ba or ba 3 ba or bab 2 a or bab 3 a 3-compresses A. 3. Let b = [x, y]\x, x ∈ {1, 2}, y = 1, 1b ∈ {1, 2} and xa ∈ {x, y}. If Orb b (1) ⊆ {1, 2}, then 1b = 2 and 2b ∈ {1, 2}, and so the word ab 2 a 3-compresses A, as M(ab 2 ) = {x, 2b}; similarly, if Orb a (x) ⊆ {x, y}, exchanging b and a and so x with 1 and y with 2, the word ba 2 b 3-compresses A. Let A be a (3, 4) 3-compressible automaton with a = [1, 2]\1 and b = [x, y]\z, zb = x. If A is proper then all the following conditions hold: 1. {1, 2} ∩ {x, z} = ∅; 2. z ∈ {1, 2} or {1, za} ∩ {x, y} = ∅; 3. {1, 1b} ∩ {x, y} = ∅; 4. 1 ∈ {x, y} or {z, 1b} ∩ {1, 2} = ∅. Proof: If {1, 2} ∩ {x, z} = ∅, then |M(b 2 a)| = 3; if z ∈ {1, 2} and {1, za} ∩ {x, y} = ∅, then |M(bab)| = 3; if {1, 1b} ∩ {x, y} = ∅, then |M(ab 2 )| = 3; if 1 ∈ {x, y} and {z, 1b} ∩ {1, 2} = ∅, then |M(aba)| = 3. So each automaton that does not satisfy one of the conditions of the lemma is 3-compressed by a word of length 3, and then it is not proper. 2 Corollary 21 Let A be a proper (3, 4) 3-compressible automaton with a = [1, 2]\1 and b = [x, y]\z, zb = x. Then exactly one of following conditions holds: 1. z = 1; 2. z = 2 and {1, 1b} ∩ {x, y} = ∅; 3. z ∈ {1, 2} and either b = [1, y]\z or b = [2, 1]\z. Proof: It is a straightforward consequence of the previous lemma. 2 Proposition 22 Let A be a (3, 4)-automaton with a = [1, 2]\1 and b = [x, y]\z, zb = x. Then A is 3-compressible and proper if and only if the following conditions hold: 1. if b = [x, y]\1, then Orb a (x) ⊆ {x, y}; 2. if z = 2 and (a) b = [1, y]\2, then Orb a (2) ⊆ {2, y} or 2ab ∈ {1, y}; (b) b = [x, 1]\2, then {2a, xa} = {2, x} or {2ab, xab} = {1, x}; (c) b = [x, y]\2, 1b = y, and 1 ∈ {x, y}, then {xa, ya} = {x, y}; 3. if z ∈ {1, 2} and (a) b = [1, y]\z and y = 2, then za = z; (b) b = [x, y]\z and {x, y} = {1, 2}, then |Orb a (z)| > 2 or zab ∈ {1, 2}. Moreover, if A is 3-compressible and proper, then either the word b 2 ab 2 or b 2 a 2 b 2 or b 2 a 3 b 2 or b 2 abab 2 3-compresses A.

Fig. 30 :

 30 Fig. 30: 3MSA for the case in which condition 1. of Proposition 22 is false.

  for the case b = [x, 1]\2, 2b = x {2a, xa} = {2, x} and {2ab, xab} = {1, x}. for the case b = [x, y]\2, 2b = x, 1b = y, 1 ∈ {x, y} and {xa, ya} = {x, y}.

Fig. 31 :

 31 Fig. 31: 3MSA for the case in which condition 2. of Proposition 22 is false.

  (a) Let condition 3.(a) be false, i.e., b = [1, y]\z, y = 2 but za = z. Then for all w ∈ a * b and u ∈ {a, b} + , M(w) = {z} and M(wu) = {1, z}, so A is not 3-compressible. (b) Let condition 3.(b) be false, i.e., b = [x, y]\z and {x, y} = {1, 2}, but |Orb a (z)| ≤ 2 and zab ∈ {1, 2}. If x = 1 and y = 2, then the 3MSA in Fig.

  for the case b = [1, 2]\z, |Orba(z)| ≤ 2 and zab ∈ {1, 2}. for the case b = [2, 1]\z, |Orba(z)| ≤ 2 and zab ∈ {1, 2}.

Fig. 32 :

 32 Fig. 32: 3MSA for the case in which condition 3.(b) of Proposition 22 is false.

Fig. 33 :

 33 Fig. 33: P3MSA for the case 2.(a) of Proposition 22.

Fig. 34 :

 34 Fig. 34: P3MSA for the case b = [x, 1]\2 and {2ab, xab} = {1, x}.

Fig. 35 :

 35 Fig. 35: P3MSA for the case b = [x, 1]\2, 2ab = 1, xab = x and {2a, xa} = {2, x}.

  (c) Let b = [x, y]\2, 1b = y, 1 ∈ {x, y} and {xa, ya} = {x, y}. Observe that if xa ∈ {x, y}, then ya ∈ {x, y}. The P3MSA in Fig. 36 proves that in this case either the word b 2 ab or b 2 abab 3-compresses A.

Fig. 36 :

 36 Fig. 36: P3MSA for the case b = [x, y]\2, 1b = y, 1 ∈ {x, y} and {xa, ya} = {x, y}.

3 .Fig. 37 :

 337 Fig. 37: P3MSA for the case b = [x, y]\z, {x, y} = {1, 2} and |Orba(z)| > 2.

( 2 )

 2 Case xa = 2 and 2b = 3.

Fig. 38 : 3 .

 383 Fig. 38: 3MSA for the case in which condition 1. of Proposition 25 is false.

  b =[3, y]\2, ya = 2 and 1b = y.

Fig. 39 :

 39 Fig. 39: 3MSA for the case in which condition 3. of Proposition 25 is false.

( 2 )

 2 Case x = 2.

Fig. 40 : 2 .Fig. 41 :

 40241 Fig. 40: 3MSA for the case in which condition 4. of Proposition 25 is false and za = 2.

Fig. 42 :

 42 Fig. 42: P3MSA for the case b = [x, 1]\2, x = 3 and 3b ∈ {x, 1}.

3 .

 3 If b = [x, 3]\2 and xa = 2 or 1b = 3, then observe that xa = 1, as 3a = 1 and x = 3. If xa = 2, then M(b 2 ) = {2, x}, M(b 2 a) = {3, xa} and |M(b 2 a 2 )| = 3. If xa = 2 and 1b = 3, then M(a 2 ) = {1, 3}, M(a 2 b) = {1b, 2} and |M(a 2 b 2 )| = 3. Then either the word b 2 a 2 or a 2 b 2 3-compresses A. If b = [3, y]\2 and ya = 2 or 1b = y, then observe that ya = 1, as 3a = 1 and y = 3. The P3MSA in Fig. 43 proves that either the word a 2 b 2 or a 2 ba 2 3-compresses A.

Fig. 43 : 2 )

 432 Fig. 43: P3MSA for the case b = [3, y]\2 and ya = 2 or 1b = y.

2 b 3 3 u ab 3 a

 333 a 2 , b 2 a 3 b 2 } is w 3 = b 2 a 3 b a 3 b 3 aba 2 v baba 2 ba 2 b 2 a 2 b 2 ab 2 aba b 2 aba 3 bab which has as a factor the word u = b 2 aba 3 bab 2 and v = a 2 b 3 aba 2 . As u belongs to the language L defined in Proposition 22, case 2.b.iii, and v belongs to the dual of L, this proves that w 3 is a 3-collapsing word of length 53.

s 3 , 2 :

 32 Qs 3,2 = {4}, Qs 3,2 = {1, 2, 4}. The word ba 3 baba 2 bab is the shortest reset word. synchronizable semiautomaton which is not 3-compressed neither by s 3,2 nor by s3,2 : Qs 3,2 = {2, 4, 5}, Qs 3,2 = {1, 3, 5}. The words ab 3 ab 3 ab 2 a, ab 2 ab 4 ab 2 a, ab 3 ab 2 ab 3 a and ab 2 ab 3 ab 3 a are the shortest reset words.

Fig. 44 :

 44 Fig. 44: Synchronizable automaton with long reset words.

Acknowledgements

We sincerely thank the anonymous reviewers for valuable comments and their careful reading of our paper, which were of great help in revising the manuscript.

The first two authors are partially supported by PRIN: "Automi e linguaggi formali: aspetti matematici e applicativi". The thirdnamed author's visit to Politecnico di Milano was supported by the CSC (China Scholarship Council), he acknowledges support from National Natural Science Foundation of China, grant No. 11261066.


Yusuke Wakabayashi

M H Upton

Stéphane Grenier

J P Hill

C S Nelson

J.-W W Kim

P J Ryan

A I Goldmann

H Zeng

J F Mitchell

A I Goldman

H Zheng

Surface effects on

systems in the coming years is the question of whether the electronic behaviour, such as charge, orbital or spin order, is different at a surface or interface compared to the bulk of the material. This question is of central importance from an applied perspective -any device one fabricates from these materials will require electron transport across an interface; from a nanoscience perspective -nanoscaled objects are defined by their very large surfaceto-volume ratio; and from a fundamental perspective -understanding the role of reduced dimensionality in determining the electronic behaviour of such systems is a key component in understanding the general problem of strongly correlated electron systems.

In many ways manganites represent an ideal system to address the role of the surface, because all the relevant degrees of freedom -charge, spin and orbital -play an active role in determining the ground state. As a result, they are exquisitely sensitive to perturbations, and hence, might be expected to exhibit relatively large surface effects. In fact, while the vast majority of experimental work has focused on bulk properties [START_REF] Tokura | Orbital Physics in Transition-Metal Oxides[END_REF][START_REF] Dagotto | Open questions in CMR manganites, relevance of clustered states and analogies with other compounds including the cuprates[END_REF], the very few surface sensitive studies do suggest that the surface of a manganite may be quite different from the bulk. For example, the measurements of Freeland et al. [START_REF] Freeland | Full bulk spin polarization and intrinsic tunnel barriers at the surface of layered manganites[END_REF] showed that the top bilayer of a cleaved surface of a ferromagnetic bilayered manganite is magnetically dead, though the second bilayer has full bulk magnetic order. Similarly, the half-doped singlelayer manganite, which is known to exhibit bulk orbital order below T OO = 231 K, showed no superlattice reflection corresponding to such ordering down to 80 K, when probed with surface-sensitive LEED [START_REF] Plummer | The next 25 years of surface physics[END_REF]. Thus, there is evidence that the surface of manganite crystals may exhibit different electronic phases than the bulk -a phenomena that has been coined 'electronic reconstruction' [START_REF] Ohtomo | Artificial charge-modulation in atomicscale perovskite titanate superlattices[END_REF][START_REF] Okamoto | Electronic reconstruction at an interface between a Mott insulator and a band insulator[END_REF] in analogy with more traditional surface science studies of atomic reconstruction driven by surface energetics.

In this paper, we present the first study of orbital order at a surface, utilizing surface xray scattering. The advantage of using x-ray scattering in this endeavour is that it provides information on both the electronic surface (specifically, atomic displacements associated with orbital order) and the chemical surface, separately. It is well known that the abrupt truncation of a sample by its surface gives rise to rod-shaped x-ray scattering around the Bragg reflections, the so-called crystal truncation rods (CTR). The intensity profiles of such rods provide detailed, quantitative information about the chemical surface [START_REF] Andrews | Scattering of x-rays from crystal surfaces[END_REF]. Similarly then, the abrupt termination of orbital order by a surface should give rise to orbital truncation rods (OTR) running through the orbital superlattice peaks. These would allow one to quantify the surface orbital order. Here, we present the first observation of such orbital truncation rod scattering. This allows us to quantitatively probe the orbital order in the vicinity of the surface. Working with a freshly cleaved La 0.5 Sr 1.5 MnO 4 , we show that the orbital order has a significantly rougher interface than the chemical surface and a shorter correlation length than in the bulk. These results imply that the surface order parameter is reduced relative to the bulk. Further, the temperature dependence of the surface orbital order suggests that the surface exhibits a more continuous transition than the bulk ordering transition. Taken together, these results demonstrate that the surface is a significant perturbation in regard to the electronic phenomena of orbital ordering and point to the need for an improved theoretical understanding of how the surface couples to such electronic orders.

We first discuss surface preparation and characterization. Single crystal samples of La 0.5 Sr 1.5 MnO 4 , which has the layered perovskite structure shown in Fig. 1 (a), were grown by the floating zone method. The samples were then either cleaved perpendicular to the c-axis in He and placed in a sealed He-filled can, or cleaved in air, and put into a closed-cycle refrigerator. Both treatments gave the same results, indicating that the surface is stable to brief exposure to air, a result also found elsewhere [START_REF] Freeland | Loss of ferromagnetism at the surface of in-sity cleaced La 1.28 Sr 1.72 Mn 2 O 7[END_REF]. Figure 1(b) shows an atomic force microscope (AFM) picture of a freshly cleaved sample. The terraces seen here are on the order of 1 μm in size, much larger than the coherence length of the x-rays. The step height observed here was 6.2 ű 0.2 Å, corresponding to c/2. We note that similar AFM pictures were obtained at the end of a week long x-ray experiment in vacuum. Analysis of the CTR intensity allows a determination of the precise termination of the cleaved sample [START_REF] You | X-ray crystal-truncation-rod analysis of untwinned YBa 2 Cu 3 O 7-δ single crystals: The growth-termination plane[END_REF]. Figure 1 (c) shows the CTR scattering intensity distribution along the (00L) and (11L) directions together with the calculated intensity distribution for a La-terminated surface and a Mnterminated surface (Fig. 1 (a)). The experimental data are well reproduced by assuming a predominantly La-terminated surface with very little surface relaxation. For comparison, there are conflicting reports in the literature for the termination of thin films, with both La and Mn termination reported [START_REF] Choi | Surfaces of the perovskite[END_REF].

As discussed above, the structure of the chemical surface is reflected in the scattering along the (hkL) direction, where h, k are integer multiples of reciprocal lattice vectors, that is rods along the surface normal c*-direction through the allowed, bulk Bragg reflections.

Similarly, scattering originating from the surface of the orbital ordering must be present in 'orbital truncation rods' -rods of scattering along the same direction but through the superlattice reflections related to the orbital order, i.e. (h + 1 4 , k + 1 4 , L) where ( 1 4 , 1 4 , 0) is the orbital ordering wave-vector [START_REF] Dheshi | Unraveling Orbital Ordering in La 0.5 Sr 1.5 MnO 4[END_REF]. One of the primary goals of this work was to observe such scattering. To this end, we measured the (20L)±( 1 4 1 4 0) intensity distribution below T OO =231 K, the bulk orbital order transition temperature. We discuss first transverse scans taken across such 'orbital rods' (figure 2 2) bulk orbital order orbital order is finite, and in fact, we find ξ bulk OO = 410 ű 8 Å, in agreement with earlier work [START_REF] Dheshi | Unraveling Orbital Ordering in La 0.5 Sr 1.5 MnO 4[END_REF]. The transverse scan taken at ( 9 4 1 4 0.2), that is across the expected OTR is shown in red. A peak is clearly observed at this position. However, this peak is not, by itself, evidence of surface scattering. Such a peak could arise from stacking faults or other defects, in the bulk orbital order which would result in a finite correlation length for the orbital order along the c-direction and hence a tail along the c*-direction for superlattice reflections.

We can, however, distinguish surface scattering from such bulk scattering by measuring the scattering intensity as a function of incidence angle α. Surface scattered intensity will be enhanced at α = θ C , the critical angle for total reflection, as a result of the interference between the incident and the scattered waves of the photon [START_REF] Feidenhans'l | Surface structure determination by x-ray diffraction[END_REF]. The inset to Fig. 2(a) shows the scattered intensity as a function of α at the bulk orbital superlattice reflection ( 7 Having established that such scattering originates from the truncation of the orbital order, we next discuss what can be learned from this new scattering. As shown in Fig. 2 (a), the transverse scan profile of the rod intensity for the chemical surface and for the orbital surface are quite different. This difference in the scattering profiles directly reflects a difference in the surface roughness. [START_REF] Andrews | Scattering of x-rays from crystal surfaces[END_REF] The sharp single peak observed for the chemical CTR scattering implies a very flat surface, and is consistent with the atomically smooth chemical surface observed in the AFM picture (Fig. 1 (b)). In contrast, the transverse profile of the orbital truncation rod exhibits two components; a 'sharp' one and a 'broad' one. Such a line shape is expected when a surface -in this case the orbital surface -has a well-defined average position (a flat plane) but local, finite deviations from this average [START_REF] Andrews | Scattering of x-rays from crystal surfaces[END_REF]. Thus, without recourse to any model-dependent fitting we can immediately conclude from the data of Fig. 2 in He, sample A, and in air, sample B) at 100K, 170K, and 200K. For the orbital rod, the intensity of the sharp component integrated in the transverse direction is shown. Note, the L-dependence of the (20L) intensity of sample A is slightly different from that of sample B, suggesting a slightly different degree of flatness of the chemical surface for the two samples.

On the other hand, the ( 9 4 1 4 L) intensity distribution for both samples is very similar and in both cases, the slope is steeper than that along (20L). This is consistent with the result in Fig. 2 (a): the orbital order surface is rougher than the chemical surface.

We next quantify this result by use of a model for a nearly flat surface due to Andrews and Cowley [START_REF] Andrews | Scattering of x-rays from crystal surfaces[END_REF]. In this model, the surface is characterized by two parameters: σ, the standard deviation of the surface height, and ξ sur , the correlation length of the surface (Fig. 3). The truncation rod intensity distribution I( Q) from such a surface is given by:

I( Q) = I s ( Q) + I b ( Q), (1)
with

I s ( Q) = 4π 2 |F ( Q)| 2 q 2 z exp(-σ 2 q 2 z )δ(h, k), (2)
and

I b ( Q) = π|F ( Q)| 2 (ξ sur ) 2 [1 -exp(-σ 2 q 2 z )] 2 σ 2 q 4 z × exp " -(ξ sur ) 2 [1 -exp(-σ 2 q 2 z )] 4σ 2 q 2 z (h 2 + k 2 ) # , (3)
where I s and I b are the intensities for the sharp component and the broad component respectively, F ( Q) is the structure factor at scattering vector Q, and q z is the c*-component of the reduced wavevector (e.g. this is 2πL/c for |L| < 0.5). In order to compare our data to the predictions of this model, we replace the delta-function in equation ( 2) with a Gaussian, to account for the finite bulk orbital correlation length, and fit the transverse scans to a two-Gaussian lineshape as shown by the red solid curve in Fig. 2 given by taking the product of the measured I(20L) and exp(-σ 2 q 2 z ), with σ=6.7 Å; here, we assumed the chemical surface is perfectly flat. The in-plane correlation length ξ sur is given by the transverse peak width and is shown in Fig. 3 (b) as a function of L, together with the L-dependence predicted by eq. ( 3) for a particular value of ξ sur . Using the value of σ = 6.7 Å, ξ sur is found to be 120 Å. That is, the surface correlation length is much shorter than that of the bulk orbital order ξ bulk OO = 410 Å. This suggests that some aspect of the surface disrupts the orbital order. This may be due to differing surface energetics resulting from the reduced coordination, or perhaps varying Sr concentrations at the site of the cleave.

We next compare the present results to that of previous reports. LEED measurements on the same material [START_REF] Plummer | The next 25 years of surface physics[END_REF] showed no superlattice intensity down to 80K, implying little orbital order is established in the topmost layer. Our result is consistent with this study. The surface roughness in the orbital order observed here necessarily requires a small order parameter or a small ordered volume fraction at the surface. The same authors also performed STM measurements on the same system and found unidentified 'electronic roughness at the surface' having an in-plane correlation length of several nanometres and surface roughness of 6 Å. Comparing to the present results, one notes that the length scale of the roughness observed in the STM study is very similar to that of the orbital order interface observed in this study, and it is tempting to surmise that this 'electronic roughness' may be related in some way to the rough orbital interface observed here. However, it is difficult to draw any firm conclusions on this point without further study.

Finally, we briefly discuss the temperature dependence of the orbital truncation rod scattering. Figure 4 shows the temperature dependence of the ( 9 4 1 4 L)-sharp component intensity for L =2, 0.2, 0.3, and 0.4 r.l.u. The temperature dependence of the surface-sensitive OTR scattering intensity (L=0.2, 0.3 and 0.4 data) is different from that of the bulk-sensitive superlattice reflection. The bulk OO transition was reported to be 'probably second order' with a relatively discontinuous transition [START_REF] Larochelle | Structural and magnetic properties of the single-layer manganese oxide La 1-x Sr 1+x MnO 4[END_REF]. In contrast, the temperature dependence of the OTR scattering intensity is seen to evolve much more continuously through the transition. The bulk superlattice reflection intensity is proportional to the volume of the orbitally ordered phase, and to the square of the order parameter, or the Jahn-Teller distortion caused by the orbital ordering. In contrast, the OTR intensity is proportional to the area of the orbital ordered flat surface and to the square of the order parameter. Since the surface roughness of the OO phase at 100K is the same as that at 200 K, then the change in in-tensity must be attributed to a change in the magnitude of the atomic displacement, i.e., in the orbital order parameter at the surface. Thus, these data suggest that the surface orbital order parameter decays more continuously than the bulk. Such phenomena may be related to surface-induced second order phase transitions that have been observed in other materials [START_REF] Watson | X-Ray Scattering Study of the Magnetic Structure near the (001) Surface of UO 2[END_REF][START_REF] Dosch | Experimental Evidence for an Interference Delocalization Transition in Cu 3 Au[END_REF]. Future work will investigate this possibility in detail.

In conclusion, we have performed a surface x-ray scattering study of a cleaved, singlelayered, half-doped manganite. The chemical surface was found to be extremely flat with a La/Sr layer termination. Importantly, we have observed the scattering arising from truncation of the orbital order at a surface for the first time. We find that the orbital surface is rougher than the chemical surface, and that its temperature dependence is different from the bulk orbital order, indicating a surface-induced second order transition. These results are further evidence of the importance of surface effects in determining electronic ground states in strongly correlated systems and provide a direct route to probe such effects quantitatively. Detailed understanding will require theoretical models capable of dealing with such surface effects explicitly. Methods X-ray diffraction measurements were performed at the beamlines X22C and X21 at the National Synchrotron Light Source, and at 6ID at the Advanced Photon Source. The measurements at X22C and 6ID were performed with 6.5 keV x-rays using a six-circle diffractometer for surface scattering experiments and those at X21 were performed with 8.8 keV

x-rays and a standard four-circle diffractometer. Most of the experiments using the six-circle diffractometers were conducted with a fixed-α mode in order to keep the illuminated sample volume constant, where α denotes the incidence angle, i.e., the angle between the crystal surface and the incident x-ray. The angle α was fixed to 0.6 • , which corresponds to a penetration depth of 600 Å, unless otherwise noted. This angle is higher than the critical angle for total reflection (θ C = 0.4 • ). The experiments at X21 were performed in a α = β mode, where β denotes the exit angle. Both modes give very similar results. The temperature was controlled by closed-cycle He refrigerators. The sample was mounted either in thermallyinsulating vacuum or in a He exchange gas. The curve fitting for CTR profile was made with the ROD program [START_REF] Vlieg | ROD: a program for surface X-ray crystallography[END_REF] with Mo for La/Sr site because the form factor of Mo approximates that of the La 0.25 Sr 0.75 mixture well.

FIG. 1 :

 1 FIG. 1: (a) The crystal structure of La 0.5 Sr 1.5 MnO 4 . Green, red and white spheres denote La/Sr, Mn, and O atoms, respectively. (b) AFM image of a cleaved sample used in this study. The step height was 6.2 ± 0.2 Å. (c) (00L) and (11L) CTR scattering intensity distribution together with the calculated intensity for La and Mn terminated surfaces. The result of the curve fitting shows the chemical surface is predominantly La terminated.

  (a)). For reference a transverse (2 δk 0.2) scan profile across the truncation rod arising from the crystallographic surface is also shown (blue data). It is as sharp as the instrumental resolution. As discussed below, this is indicative of a smooth atomic surface. The open circles show the profile of the ( 9 4 1 4

1 4 2 )

 12 3) has a maximum around θ C = 0.4 • while a smooth increase is seen at (74 with increasing α, a result of the fact that more of the beam is intercepted by the sample at higher angles. Since the exit angle β for ( 1.5 degrees in this scan region, the observed intensity maximum cannot be due to a maximum in the sample illumination and detector acceptance, which happens at α = β in our experimental configuration. Therefore, we conclude that the scattering observed at (, shown in Fig.2(a) does indeed come from surface scattering and not from stacking faults or other bulk effects. This is the first such observation of the orbital truncation rod scattering.

  (a). The L-dependence of the parameters derived from these fits are shown in Figure3(a), which plots the ratio of the intensity of the broad component and the sharp component, and in Figure 3(b), which shows the widths of the two components, for the 170 K data set. The intensity ratio I b /I s increases rapidly with L. This ratio depends mainly on σ, and hence σ may be obtained from the plot. The solid line in Fig. 3(a) shows the expected behaviour for σ = 6.7 Å, which reproduces the data quite well. Note, this same value of σ is also consistent with the results shown in Fig. 2 (b); The solid line in this latter figure is the calculated intensity distribution

FIG. 3 :

 3 FIG. 3: (a) The intensity ratio of the broad component observed in the transverse orbital truncation rod scans to the sharp component, as a function of L. (inset) Schematic view of the orbital order region around the surface. (b) Peak widths of broad-and sharp-component. Calculated values for the model discussed in the text are shown by solid lines in both figures.

FIG. 4 : 1 4

 41 FIG. 4: Temperature dependence of the ( 9 4

Acknowledgement We thank Dr. A. Checco for helping with AFM measurements. Y.W. wishes to acknowledge the Yamada Science Foundation, support for long-term visit. US DOE, Basic Energy Sciences supported work at Brookhaven under contract No. DE-AC02-98CH10886, at Argonne under contract No. W-31-109-Eng-38, and at the MUCAT Sector at the Adcanced Photon Source and Ames Laboratory under contract No. DE-AC02-07CH11358.

(a) that there exists a flat chemical surface and a rougher orbital order surface.

A rougher surface also has the consequence that the intensity along the truncation rod must fall more sharply as a function of L than for a less rough surface.