Marie-Pierre Béal

Sylvain Lombardy

Dominique Perrin

Embeddings of local automata

We prove that any local irreducible automaton is contained in a complete one. The proof uses Nasu's masking lemma. We use the same technique to give a new proof that any weakly deterministic irreducible automaton is contained in a complete one.

Introduction

The problem of embedding a finite automaton into one having specified properties is an old one in automata theory (see [START_REF] Schützenberger | A remark on incompletely specified automata[END_REF] for example). We will consider here the problem of embedding an automaton into a complete one for several families of automata including local and weakly deterministic automata.

In symbolic dynamics, the problem of embedding a shift into another shift has been studied extensively. A necessary and sufficient condition for the strict embedding of shifts of finite type has been given by Krieger (Krieger's Embedding Theorem [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]).

The problem of embedding an unambiguous irreducible automaton into a complete one has been solved in [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF] using a construction due to Ehrenfeucht and Rozenberg [START_REF] Ehrenfeucht | Each regular code is included in a regular maximal code[END_REF]. This result has a formulation in terms of codes. Indeed, the stabilizer of a state in an unambiguous automaton is a free submonoid. Thus the above embedding implies that any rational code is contained in a maximal one (the Ehrenfeucht-Rozenberg Theorem).

A local automaton is by definition such that a bounded information about the past and the future is enough to determine the present state. Formally there 1 are integers λ, ρ such that for any pair of paths p u → q v → r and p ′ u → q ′ v → r ′ having the same label with |u| = λ and |v| = ρ one has q = q ′ . A subautomaton of a local automaton is obviously still local but conversely it is not clear how one can add transitions or states to a local automaton until it is complete, in the sense that any word on the underlying alphabet is the label of a path.

The problem of completing local automata has already been considered in [START_REF] Montalbano | Local automata and completion[END_REF], where a method is given which allows one to complete a local deterministic automaton when it is possible. We prove here that any local automaton is always contained in a complete one. The stabilizer of a state in a local automaton is the star of a locally parsable code (also called codes with finite synchronization delay). The previous result gives an alternative proof of a result of Bruyère according to which any locally parsable rational code is included in a maximal one [START_REF] Bruyère | On maximal codes with bounded synchronization delay[END_REF], see also [START_REF] Berstel | Codes and Automata[END_REF].

Our proof relies on a result known as Nasu's Masking Lemma [START_REF] Nasu | Topological conjugacy for sofic systems and extensions of automorphisms of finite subsystems of topological markov shifts[END_REF]. This result deals with the embedding of a shift of finite type into another one and gives a complement to Krieger's Embedding Theorem. Given a graph G, the edge shift on G is the set X G of biinfinite paths in G. The result states that if X G can be embedded in X H , then there is a graph K such that X K is isomorphic to X H and G is contained in K. We use this result in the particular case where X H is the full shift but the same proof can be used to obtain a more general result with an arbitrary subshift instead of the full shift.

We also use Nasu's masking lemma to give a new proof of a result of [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF] concerning weakly deterministic automata, which are such that the knowledge of the starting state and of a prefix of length d of the label of a path determines its first edge. These automata are also called right-closing in symbolic dynamics. We give a new proof using Nasu's lemma that any d-weakly deterministic automaton is contained in a complete one. This result can be reformulated in terms of codes. The basis of the stabilizer of a state in a weakly deterministic automaton is, by definition, a weakly prefix code (also called codes with finite deciphering delay).

We have written this paper in a self-contained form and in particular we adapt the proof of Nasu's lemma to our notation.

A first version of this paper was presented at the IEEE International Symposium on Information Theory [START_REF] Béal | Embeddings of local automata[END_REF].

Equivalences of automata

We denote by A = (Q, E) a finite automaton on the alphabet A with Q as set of states and E ⊂ Q × A × Q as set of edges. We consider all states as both initial and terminal. The automaton is said to be complete (with respect to the alphabet A) if for any word w ∈ A * there exists a path labelled w. It is said to be unambiguous if for any p, q ∈ Q and w in A * there is at most one path from p to q labelled w. It is said to be irreducible if for any p, q ∈ Q there is at least one word w such that there is a path from p to q labelled w.

An automaton is said to be essential if any state has at least one incom-ing edge and at least one outgoing edge. Clearly an irreducible automaton is essential.

An automaton A = (P, E) on the alphabet A is a subautomaton of an automaton B = (Q, F ) on the alphabet A, if P ⊂ Q and E ⊆ F ∩ (P × A × P ).

An automaton is deterministic if for each state p and each letter a there is at most one edge labelled a going out of p. We use the notation p • a = q to express the fact that there is an edge p a → q in a deterministic automaton. It can be shown that an irreducible deterministic automaton is complete if and only if for each state p and letter a there is exactly one edge labelled a going out of p.

The transition matrix of an automaton A = (Q, E) is the Q × Q matrix with elements in the set P(A) of subsets of A defined for p, q ∈ Q by M p,q = {a ∈ A | there is an edge (p, a, q) in E}.

The elements of M can be considered as elements of the semiring P(A * ) of subsets of A * , where 0 is the empty set and 1 is the set containing the empty word. Such matrices can therefore be multiplied.

Let A = (P, E) and B = (Q, F ) be two automata on the alphabet A. Let M be the transition matrix of A and let N be the transition matrix of B. We say that A and B are elementary equivalent if there exist a (P × Q)-matrix R and a (Q × P )-matrix S both with elements in P(A) ∪ {1}, where 1 is the empty word, such that M = RS and N = SR. We also say that A is (R, S)-elementary equivalent to B.

This notion is classical in symbolic dynamics. It is usually formulated for subshifts of finite type (see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF] p. 225). Our definition is a particular case of the notion of symbolic elementary equivalence for sofic shifts introduced in [START_REF] Nasu | Topological conjugacy for sofic systems[END_REF].

For a P × Q-matrix R with elements in P(A) ∪ {1}, we say that a triple (p, a, q) ∈ P × (A ∪ {1}) × Q is an R-edge (resp. an S-edge) when a ∈ R p,q (resp. a ∈ S p,q ). Thus when A is (R, S)-equivalent to B, each edge of A is the sequence of an R-edge and a consecutive S-edge, and each edge of B is a sequence of an S-edge and a consecutive R-edge. The R-edges and S-edges can be considered as edges of a bipartite graph called the auxiliary graph of the equivalence (it is called a bipartite code in [START_REF] Nasu | Topological conjugacy for sofic systems[END_REF] and [7, p. 355]). Let A = (Q, E) be an automaton. The input of a state q ∈ Q is the set of pairs (p, a) such that one has p a → q. Its output is the set of pairs (a, r) such that one has q a → r. An input merge equivalence is an equivalence on the set Q of states of A such that for any pair p, p ′ of equivalent states, any letter a and any state q, one has

(i) p a → q if and only if p ′ a → q, (ii) q a → p, q a → p ′ implies p = p ′ .
Thus, in such an equivalence, two equivalent and distinct states have the same output and disjoint inputs. The quotient of A = (Q, E) by such an equivalence is the automaton A = (Q, E) with states the set Q of equivalence classes, and edges the induced edges on the classes, i.e. (p, a, q) ∈ E for some p, q ∈ Q implies that (p, a, q) is in E.

Thus, in the quotient the output of a class of states is the common output of its elements and its input is the union, or merge, of the inputs of its elements (whence the name of an input merge equivalence). We say that A is obtained from A by an input merge. We also say that A is obtained from A by an input split .

Note that if A is an unambiguous essential automaton, there is a largest input merge equivalence. It is defined by q ≡ q ′ if q and q ′ have the same output. Indeed, since A is essential, if q ≡ q ′ , they have the same non-empty output. Since it is unambiguous, they have disjoint inputs.

Example 2 Let A, B be the automata of Example 1. The automaton A is obtained from B by an input merge.

An output merge equivalence on the set of states of an automaton A is defined symmetrically. It is an equivalence on the set Q of states such that equivalent and distinct states have the same input and disjoint outputs. The quotient A is defined in the same way by merging the outputs of the elements of a class. We say that A is obtained from A by an output merge. We also say that A is obtained from A by an output split .

Observe that the quotient of an automaton A by an input or an output merge equivalence is unambiguous if and only if A is unambiguous.

The notions of input and output merge equivalence are classical in symbolic dynamics. They are usually formulated for subshifts of finite type (see [7, p. 225]). The extension of the definitions to sofic shifts is due to Nasu [START_REF] Nasu | Topological conjugacy for sofic systems[END_REF]; see also [START_REF] Krieger | On sofic systems[END_REF].

The following result is an element of William's Classification Theorem (see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]).

Proposition 1 If the automaton A is obtained from the automaton B by an input (or output) merge, then A and B are elementary equivalent.

Proof We treat the case of an input merge. Let B = (Q, E) and A = (Q, E). Let M and N be the transition matrices of A and B. Let R be the Q×Q-matrix defined for p, q ∈ Q by R p,q = {a ∈ A | there is an edge (p, a, q) in E} (note that R is well-defined because of the definition of an input merge). Let S be the Q × Q-matrix defined by S p,q = 1 if p = q 0 otherwise Then M = RS and N = SR. Thus A and B are elementary equivalent.

Proposition 2 Let A and B be two irreducible (R, S)-elementary equivalent automata. Then, either R has elements in P(A) and S in {0, 1} or conversely.

Proof Set A = (P, E) and B = (Q, F ). Suppose that there are p ∈ P , a ∈ A, and q ∈ Q such that a ∈ R pq . Let p ′ ∈ P and q ′ ∈ Q. We denote s = S q ′ p ′ . Let us show that, if s = 0 then s = 1. Since B is irreducible, there is path q u → q ′ labelled by u = a 1 . . . a n . We have a i = s i r i , for 1 ≤ i ≤ n, with r i ∈ R piqi , and s i ∈ S qi-1pi , and thus the path

p a → q 0 s1 → p 1 r1 → q 1 s2 → • • • sn → p n rn → q n s → p ′ ,
with q 0 = q and q n = q ′ . Since as 1 is the label of an edge in E, s 1 = 1. Since s 1 r 1 is the label of an edge in F , r 1 ∈ A and so on. Finally r n ∈ A and thus s = 1.

This shows that if one entry of R contains an element of A then all the entries of S are 0 or 1. Furthermore, if all the entries of S are 0 or 1, then all non-null entries of R are in P(A). The proof of the symmetrical case is similar.

We denote by L(A) the set of words labelling a finite path in A. Two automata A and B are said to be equivalent if L(A) = L(B).

We say that two automata A and B are strongly equivalent if there is a sequence A 0 , A 1 , . . . , A n of automata such that

A 0 = A, A n = B and A i is elementary equivalent to A i+1 for 0 ≤ i ≤ n -1.
Proposition 3 Two strongly equivalent essential automata are equivalent.

Proof Let A = (P, E) and B = (Q, F ) be (R, S)-elementary equivalent automata on the alphabet A. Let w = a 1 . . . a n ∈ L(A). Since A is essential, there is a path p -1 a0 → p 0 a1 → p 1 a2 → • • • p n-1 an → p n an+1 → p n+1 ,
with a 0 , a n+1 ∈ A. For each i = 0, . . . , n + 1, we have

a i = r i s i with r i ∈ R pi-1qi
and s i ∈ S qipi , and thus a path

p -1 r0 → q 0 s0 → p 0 r1 → q 1 s1 → p 1 • • • p n-1 rn → q n sn → p n rn+1 → q n+1 sn+1 → p n+1
using alternately entries of R and S. Then either r 0 = a 0 , . . . , r n+1 = a n+1 and

s 0 = • • • = s n+1 = 1 or r 0 = • • • = r n+1 = 1 and s 0 = a 0 , . . . , s n+1 = a n+1 .
We consider the first case, the other one being symmetrical. Since SR is the transition matrix of B, we have in B a path

q 0 a1 → q 1 a2 → • • • an → q n an+1 → q n+1 .
This shows that wa n+1 ∈ L(B) and thus w ∈ L(B).

We will now describe a construction due to Nasu (see [7, p. 354], Lemma 10.2.3). It associates to automata A 1 , A 2 , B 1 such that A 1 is elementary equivalent to A 2 and A 1 is a subautomaton of B 1 , an automaton B 2 elementary equivalent to B 1 and such that A 2 is a subautomaton of B 2 . The automaton B 2 is called the Nasu embedding of A 2 with respect to A 1 , B 1 .

Set

A 1 = (P 1 , E 1 ), A 2 = (P 2 , E 2 ) and B 1 = (Q 1 , F 1 )
. Let R, S be matrices such that RS and SR are respectively the transition matrices of

A 1 and A 2 . Let Q 2 = P 2 ∪ (F 1 \ E 1 ). We define a Q 1 × Q 2 -matrix R and a Q 2 × Q 1 -matrix S as follows.
Suppose first that R has 0, 1 entries and S entries in P(A). Then, for

q 1 ∈ Q 1 and q 2 ∈ Q 2 , we define R q1,q2 =    R q1,q2 if q 1 ∈ P 1 , q 2 ∈ P 2 1 if q 2 ∈ F 1 \ E 1 and o(q 2 ) = q 1 0 otherwise and S q2,q1 = S q2,q1 ∪ {l(q 2 ) | q 2 ∈ F 1 \ E 1 , e(q 2 ) = q 1 },
where o(q 2 ) denotes the origin of q 2 , l(q 2 ) its label, and e(q 2 ) its end. An illustration of this construction is given in Example 3.

In the case where R has entries in P(A) and S has 0, 1 entries, we define

R q1,q2 = R q1,q2 ∪ {a ∈ A | q 2 ∈ F 1 \ E 1 , o(q 2 ) = q 1 , l(q 2 ) = a} and S q2,q1 =    S q2,q1 if q 1 ∈ P 1 , q 2 ∈ P 2 1 if q 2 ∈ F 1 \ E 1 and e(q 2 ) = q 1 0 otherwise .
It is clear that in both cases, R S is the transition matrix of B 1 . The automaton B 2 = (Q 2 , F 2 ) is defined by its transition matrix which is S R. To sum up, we have the following statement. (resp. B i ) of Figure 3, we have

Proposition 4 Let A 1 , A 2 , B 1 be automata such that A 1 is a subautomaton of B 1 and A 1 is elementary equivalent to A 2 . Let B 2 be the Nasu embedding of A 2 with respect to A 1 , B 1 . Then A 2 is a subautomaton of B 2 and B 1 is elementary equivalent to B 2 . Moreover, if A 2 and B 1 are irreducible (resp. essential), then B 2 is irreducible (resp. essential).
B 1 = (Q 1 , F 1 ) with Q 1 = {2, 3, 4} and B 2 = (Q 2 , F 2 ) with Q 1 = {1, c,
M 1 = a b a b = RS = 1 1 a b , M 2 = a + b = SR. N 1 =   a b 0 a b c 0 d 0   = R S =   1 0 0 1 1 0 0 0 1     a b 0 0 0 c 0 d 0   , N 2 =   a + b b 0 0 0 c d d 0   = S R =   a b 0 0 0 c 0 d 0     1 0 0 1 1 0 0 0 1   .
The following result will be used in Section 4.

Proposition 5 Let A 1 , A 2 , A 3 , B 3 be essential automata such that A 1 is an input merge of A 2 , A 3 is an output merge of A 2 and A 3 is a subautomaton of B 3 .

B 1 ∩ A 1 B 2 ∩ A 2 B 3 ∩ A 3
Let B 2 be the Nasu extension of A 2 with respect to

A 3 , B 3 . Then A 1 is a subautomaton of the maximal input merge B 1 of B 2 . Proof Set A i = (P i , E i ) for i = 1, 2, 3 and let B i = (Q i , F i ) for i = 2, 3. Let M i be the transition matrix of A i for i = 1, 2, 3. Set M 2 = SR, M 3 =
RS and let R, S be the matrices corresponding to the Nasu extension of A 2 . We have

Q 2 = P 2 ∪ (F 3 \ E 3 ) and for q 2 ∈ Q 2 , q 3 ∈ Q 3 , S q2,q3 = S q2,q3 ∪ {l(q 2 ) | q 2 ∈ F 3 \ E 3 , e(q 2 ) = q 3 } and R q3,q2 =    R q2,q3 if q 2 ∈ P 2 , q 3 ∈ P 3 1 if q 2 ∈ F 3 \ E 3 and o(q 2 ) = q 3 0 otherwise
Let p 2 , p ′ 2 ∈ P 2 be two states of A 2 that have the same output. Let us show that they also have the same output in B 2 . For this, suppose that (p 2 , a, r) is an edge of B 2 with r ∈ F 3 \ E 3 . Since the transition matrix of B 2 is S R, there is a state q ∈ Q 3 such that a ∈ S p2q and R qr = 1. It follows from the definition of S that q is in P

3 (indeed if q ∈ Q 3 \ P 3 , then p 2 ∈ F 3 \ E 3 , a contradiction).
Since A 3 is obtained from A 2 by an output merge, there is a p ∈ P 2 such that R q,p = 1 and thus an edge (p 2 , a, q) in E 2 . Since p 2 , p ′ 2 have the same input in A 2 , we have also an edge (p ′ 2 , a, q) in E 2 . Thus there is an edge (p ′ 2 , a, r) in F 2 , which proves the assertion.

This shows that the automaton B 1 obtained from B 2 by merging the states with the same output, has A 1 as a subautomaton.

Local automata

An automaton is said to be (λ, ρ)-local if for all pairs of paths p u → q v → r and p ′ u → q ′ v → r ′ with |u| = λ and |v| = ρ, one has q = q ′ . The automaton is said to be local if it is (λ, ρ)-local for some λ, ρ ≥ 0. An automaton which has a single state is (0, 0)-local.

Thus in a local automaton, one can recover a biinfinite path from its label using a sliding window of fixed size.

As a particular case of a local automaton, an edge automaton is such that all edges have distinct labels. An edge automaton is both (0, 1) and (1, 0)-local.

A word w is said to be a constant for an automaton A if for p, p ′ , q, q ′ ∈ P such that p w → q and p ′ w → q ′ one has also p w → q ′ and p ′ w → q. The empty word is a constant only when the automaton has a single state.

Observe that when the automaton is deterministic, a constant is a word w such that the set Im(w) = ∈ P | p w → q for some p ∈ P } has at most one element.

The following result from [START_REF] Montalbano | Local automata and completion[END_REF] gives a necessary a property of irreducible complete deterministic local automata. This property can be used to show that some local deterministic automata are not contained in a complete irreducible one (see Example 6).

Proposition 6 Let A be is an irreducible complete deterministic local automaton on the alphabet A with more than one state. Then a∈A Im(a) = ∅, Proof Suppose that q ∈ a∈A Im(a). Let w be a word of maximal length which is not a constant. Then for each letter a ∈ A, the word aw is a constant and thus Im(aw) has only one element. Thus for any state p we have p • w = q • w. Indeed, since A is essential, there is a letter a such that p ∈ Im(a). Then p, q ∈ Im(a), which implies p • w = q • w. This contradicts the fact that w is not a constant. Note that if A is a (λ, ρ)-local automaton, then an input split of A is a (λ + 1, ρ)-local automaton, and an output split of A is a (λ, ρ + 1)-local automaton.

Proposition 7 An irreducible automaton is local if and only if it is unambiguous and there exists an integer n such that any word of length n is a constant. Proof Suppose first that A is (λ, ρ)-local. Let c, c ′ be two paths from p to q labelled w. Since A is irreducible, there exist states r, s and paths r u → p, q v → s with |u| = λ and |v| = ρ. Since A is (λ, ρ)-local, the paths c, c ′ coincide. Thus A is unambiguous. Suppose next that p w → q and p ′ w → q ′ with |w| = λ + ρ. Let w = uv with |u| = λ and |v| = ρ. Let r, r ′ be such that

p u → r v → q and p ′ u → r ′ v → q ′ . Since A is (λ, ρ)-local, we have r = r ′ .
This implies that we also have paths p w → q ′ and p ′ w → q. Thus the condition of the statement is true with n = λ + ρ.

Conversely, let us assume that any word of length n is a constant and that

A is unambiguous. Let us show that A is (n, n)-local. Suppose that p u → q v → r and p ′ u → q ′ v → r ′ with |u| = |v| = n.
Then, since u and v are constants, we also have p u → q ′ v → r. Since A is unambiguous, this forces q = q ′ , whence the conclusion.

The least integer n such that any word of length n is a constant is called the order of the automaton. Note that a (λ, ρ)-local automaton has order at most λ + ρ. It can however be strictly less than λ + ρ. An unambiguous automaton with order n is (n, n)-local.

Let λ, ρ ≥ 0. The free (λ, ρ)-local automaton is the automaton with set of states consisting of pairs (u, v) of words, with u of length λ and v of length ρ, and edges the triples ((u, v), a, (u ′ , v ′ )) such that there are letters b, c with uvc = bu ′ v ′ and a is the first letter of vc (and also the last letter of bu ′ ). It is clear that this automaton is (λ, ρ)-local.

The free (n, 0)-local automaton is usually known as the de Bruijn automaton of order n.

Lemma 1 Let n be a nonnegative integer such that λ, ρ ≤ n, the free (λ, ρ)-local automaton has order n.

Proof Let F (λ,ρ) be the free (λ, ρ)-local automaton. Let (u, v) w → (x, y) and (u ′ , v ′ ) w → (x ′ , y ′ ) be two paths labelled w of length n in F (λ,ρ) , with u, u ′ , x, x ′ of length λ and v, v ′ , y, y ′ of length ρ. Since λ, ρ ≤ n, v, v ′ are prefixes of w and x, x ′ are suffixes of w. Hence v = v ′ and x = x ′ and there are paths (u, v)

w → (x, y ′ ) and (u ′ , v) w → (x, y) in F (λ,ρ) .
Example 5 The free (1, 1)-local automaton on the alphabet {a, b} is represented on Figure 5. The label of an edge going out of a state is its second letter.

The following result shows that any (λ, ρ)-local automaton is strongly equivalent to a subautomaton of the free (λ, ρ)-local automaton. Proposition 8 If A is (λ, ρ)-local automaton, there is a sequence A 0 , A 1 , . . . , A λ+ρ of (λ, ρ)-local automata such that

(i) A 0 = A.
(ii) For i = 0, . . . , λ -1, A i is obtained from A i+1 by an input merge.

(iii) For i = λ, . . . , λ + ρ -1, A i is obtained from A i+1 by an output merge.

(iv) A λ+ρ is a subautomaton of the free (λ, ρ)-local automaton.

Proof Let A = (P, E). We define for 1 ≤ i ≤ λ, A i = (P i , E i ) where P i is the set of pairs (u, q) with u ∈ A i and q ∈ Q such that there is a path labelled u leading to q in A. There is an edge labelled a from (u, p)

to (v, q) in A i if u = bu ′ , v = u ′ a for b ∈ A and (p, a, q) ∈ E. For j = 1, . . . , ρ, let A λ+j = (P λ+j , E λ+j )
where P λ+j is the set of triples (u, p, v) ∈ A λ × P × A j such that there is a path labelled u leading to p and a path labelled v leaving p in A. There is an edge labelled a from (u, p, v) to (w, q, t) if and only if

u = bu ′ , w = u ′ a, v = av ′ , t = v ′ c and (p, a, q) ∈ E.
For 0 ≤ i ≤ λ -1, the equivalence θ i+1 on P i+1 defined by (u, p) ≡ (u ′ , p ′ ) if p = p ′ and u, u ′ differ at most by the first letter is an input merge. Similarly, for λ ≤ i ≤ λ + ρ -1, the equivalence θ i+1 on P i+1 defined by (u, p, v) ≡ (u ′ , p ′ , v ′ ) if u = u ′ , p = p ′ and v, v ′ differ at most by their last letter, is an output merge. This shows that conditions (ii) and (iii) are satisfied.

Finally, since A is (λ, ρ)-local, in a state (u, p, v) of A λ+ρ , the state p is determined by (u, v). Thus condition (iv) is also satisfied.

Observe that if A is moreover supposed to be irreducible, then all the automata A i constructed as above are also irreducible.

We will prove the following result.

Theorem 2 Any local local irreducible automaton is a subautomaton of a complete one with the same order.

The proof uses Nasu embeddings. We will deduce Theorem 2 from the following more precise statement.

B 1 , with a, a ′ ∈ A, such that π(d) = c and π(d ′ ) = c ′ . Since B 1 has order n, w is a constant for B 1 . Thus we have also paths e

= r w → s ′ a ′ → t ′ and e ′ = r ′ w → s a → t in B 1 .
It is easy to verify that π(e) is a path from p to q ′ and π(e ′ ) a path from p ′ to q. Thus w is a constant for B 2 .

Proof of Proposition 9. Let A be an irreducible (λ, ρ)-local automaton. By Proposition 8 there is a sequence A 0 , A 1 , . . . , A λ+ρ of automata such that A = A 0 , A λ+ρ is a subautomaton of the free (λ, ρ)-local automaton and each A i is a merge of A i+1 . By Lemma 1, the free (λ, ρ)-local automaton has order n = max(λ, ρ). Since A λ+ρ is included in the free (λ, ρ)-local automaton, we may build using repeatedly Proposition 10 a sequence B λ+ρ , . . . , B 1 , B 0 of complete local irreducible automata with order n such that A i is contained in B i for i = λ + ρ, . . . , 0. Thus B = B 0 is a complete local automaton with order n containing A. Since A is irreducible, all A i and B i are irreducible.

Example 6 Let A = A 0 be the deterministic automaton represented on the left of Figure 6. It is (3, 0)-local and has order 3. Indeed, the action of a, b on the set of states represented on the right of Figure 6 shows that any word of length 3 has an image of cardinality at most 1. Note that A cannot be completed in a local deterministic automaton by Proposition 6. Indeed, we have 2 ∈ Im(a) ∩ Im(b).

We have represented on Figure 7 a split A 1 of A, obtained by an input split of state 2 in two states 5 and 7. This automaton can easily be completed as indicated on Figure 7.

The matrices R, S such that the transition matrix of A 1 is RS and the transition matrix of A is SR are

R =     1 0 0 0 1 0 0 0 1 0 1 0     , S =   0 a 0 b 0 0 b 0 a 0 0 0   .
The auxiliary graph is shown on Figure 8. The final result is shown on Figure 9. It is a complete local automaton containing A. To check that it is complete, one can apply the subset construction to build an equivalent deterministic automaton. Since A is irreducible and local, this construction may be started from any state. Then we can check that each state has outgoing edges carrying each letter.

Weakly deterministic automata

An automaton A is said to have delay d if for any pair of paths

p a → q z → r, p a → q ′ z → r ′ ,
with a ∈ A, z ∈ A * and |z| = d then q = q ′ . We say that the automaton is weakly deterministic if it has delay d for some integer d ≥ 0. The minimal delay of an automaton A is the least integer d such that A has delay d.

Weakly deterministic automata are also known in symbolic dynamics as right-closing labeled graph.

Thus a deterministic automaton has delay 0. Observe that if A has delay d, then for any word w, and for any pair of paths

p w → q z → r, p w → q ′ z → r ′ ,
with w, z ∈ A * and |z| = d, the paths p w → q and p w → q ′ are equal.

Proposition 11 Let A be an essential automaton. If A is local, it is weakly deterministic. If it is weakly deterministic, it is unambiguous.

Proof Suppose first that A is (λ, ρ)-local. Let p a → q z → r and p a → q ′ z → r ′ be paths with |z| = ρ. Since A is essential, there exists a path s y → p with |ya| ≥ λ. Since we have paths s ya → q z → r and s ya → q ′ z → r ′ , we have q = q ′ . Thus A has delay ρ.

Suppose next that A is has delay d. Two paths from p to q with the same label may be extended to the right arbitrarily. This forces them to coincide. Thus A is unambiguous.

We will use the following result.

Proposition 12 Let A 1 and A 2 be (R, S)-strongly equivalent irreducible automata. If the automata A 1 is weakly deterministic, then A 2 also, and their minimal delays differ at most by one.

Proof Let us suppose that A 2 has delay d -1 and show that A 1 has delay d. We treat the case where the entries of R are in P(A) and the entries of S are in {0, 1}. The other case is similar.

Let

p 0 a0 → p 1 a1 → • • • p d → p d+1 and p 0 a0 → p ′ 1 a1 → • • • a d
→ p ′ d+1 be two paths in A 1 of length d + 1 with the same origin and the same label a 0 a 1 • • • a d , with a i ∈ A. Since A 1 is irreducible, there exists an S-edge q 0 → p 0 . Thus we have, in the auxiliary graph, paths q 0 → p 0 a0

→ q 1 → p 1 a1 → q 2 • • • a d → p d+1 and q 0 → p 0 a0 → q ′ 1 → p ′ 1 a1 → q ′ 2 • • • a d → p ′ d+1 .
Since A 2 has delay (d -1), we have q 1 = q ′ 1 and q 2 = q ′ 2 . This implies p 1 = p ′ 1 . Thus A 1 has delay d. The following statement shows that an input merge cannot increase the delay.

Proposition 13 Let A 1 be an input merge of A 2 . Then A 1 and A 2 have the same minimal delay.

Proof The delay of a (input or output) merge cannot be larger than the original one. Hence if A 2 has delay d, then A 1 has delay d. Conversely, suppose that A 1 has delay d. Let p a → q u → r and p a → q ′ u → r ′ be two paths in A 2 where a ∈ A and u ∈ A d . We then have paths p a → q u → r and p a → q′ u → r ′ in A 1 . Since A 1 has delay d, we have q = q′ . Since the inputs of q and q ′ are not disjoint, we have q = q ′ . Thus A 2 has delay d.

The following result, which already appears in [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF], is the analogue of Theorem 2 for weakly deterministic automata. The proof uses again Nasu embeddings.

Theorem 3 A weakly deterministic irreducible automaton is a subautomaton of a complete one with the same delay.

Observe that, contrary to Theorem 2, the above statement is trivial if the result is not required to be irreducible.

We first prove the following result which shows that a weakly deterministic irreducible automaton is strongly equivalent to a deterministic irreducible automaton.

Proposition 14 If A is a weakly deterministic irreducible automaton with delay d ≥ 1, there exist automata A 1 and A 2 such that A is an input merge of A 1 , A 2 is an output merge of A 1 and A 2 has delay d -1.

Proof Set A 0 = A and A i = (P i , E i ) for i = 0, 1, 2. Let P 1 = E 0 and let E 1 be the set of triples (e, a, f ) with e, f ∈ E 0 and a ∈ A such that e, f are consecutive edges of A and a is the label of f . In this way, there is an input merge from A 1 to A 0 obtained by merging the states with the same third component. The particular solution given in [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF] is not the same as the one described above. Let us explain how it works on this example.

The embedding is based on the observation that an automaton with delay d is complete if and only if for each state p the following condition is satisfied: for each word u of length d such that there is a path labelled u starting at p, there also a path labelled ua starting at p for each a ∈ A.

Since state 2 can be followed by ba but not by bb, we add an edge labelled b from 2 to a new state called b and such that there is an edge labelled b going to state 1. Further, since state b can be followed by ba but not by bb, we add a loop labelled b on state b. The above condition is now satisfied for any state. Let B 0 be the complete automaton thus obtained.

This automaton is obtained by the previous construction starting with the The full statement of the result of [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF] is more general and Theorem 3 and its proof can be extended as follows. Let A be an irreducible edge automaton. Any weakly deterministic irreducible automaton B such that L(B) ⊆ L(A) is a subautomaton of a weakly deterministic irreducible automaton C which is equivalent to A and has the same delay.

We have not been able to found a way to prove by Nasu extensions the analogous result of [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF] concerning bi-closing automata, i.e. which have finite delay in both directions.

Example 1

 1 Let A and B be the automata represented on Figure1.

Figure 1 :

 1 Figure 1: Two elementary equivalent automata A (on the left) and B (on the right). The transition matrices M and N of A and B are M = [a + b] , N = a b a b .

1 Figure 2 :

 12 Figure 2: The auxiliary graph (with continuous edges).

Example 3 Figure 3 :

 33 Figure3: The Nasu embedding B 2 of A 2 with respect to A 1 , B 1 . The automata A 1 = (P 1 , E 1 ) with P 1 = {2, 3} and A 2 = (P 2 , E 2 ) with P 2 = {1} are represented with continuous edges. We haveB 1 = (Q 1 , F 1 ) with Q 1 = {2, 3, 4} and B 2 = (Q 2 , F 2 ) with Q 1 = {1,c, d}. The automaton B 2 has two additional states c, d corresponding to the additional edges (3, c, 4) and (4, d, 3) of B 1 . The transitions defined by R and S are represented with dashed edges. Additional states and edges are represented with dots.

  Figure3: The Nasu embedding B 2 of A 2 with respect to A 1 , B 1 . The automata A 1 = (P 1 , E 1 ) with P 1 = {2, 3} and A 2 = (P 2 , E 2 ) with P 2 = {1} are represented with continuous edges. We haveB 1 = (Q 1 , F 1 ) with Q 1 = {2, 3, 4} and B 2 = (Q 2 , F 2 ) with Q 1 = {1,c, d}. The automaton B 2 has two additional states c, d corresponding to the additional edges (3, c, 4) and (4, d, 3) of B 1 . The transitions defined by R and S are represented with dashed edges. Additional states and edges are represented with dots.

Example 4 Figure 4 :

 44 Figure 4: A (1, 1)-local automaton.

Figure 5 :

 5 Figure 5: The free (1, 1)-local automaton. It has order 1.

Figure 6 :

 6 Figure 6: A local automaton A and the action on subsets.

Figure 7 :

 7 Figure 7: A split A 1 of A and its completion B 1 with the dotted edges.

Figure 8 :

 8 Figure 8: The auxiliary graph (with continuous edges). The automata A and A 1 are represented with dashed edges and the additional edges with dotted lines.

Figure 9 :

 9 Figure 9: The result is the embedding of A with respect to A 1 and B 1 . This automaton has order 3 although it is (3, 1)-local.

Figure 10 :

 10 Figure 10: The local automata B, C on the left (with the additional dotted edge for C), and A on the right.

Let A 2 Figure 11 :Example 8 Figure 12 :

 211812 Figure 11: The construction in the proof of Proposition 14. The delay of each automaton is given inside the parenthesis.

Figure 13 :

 13 Figure 13: Another embedding of the previous automaton.

Acknowledgements: We would like to thank Brian Marcus who pointed out to us the possibility of using Nasu's masking lemma in this problem.

Proposition 9 Any irreducible (λ, ρ)-local automaton is a subautomaton of a complete irreducible local automaton of order max(λ, ρ).

Note that it is not true that any irreducible (λ, ρ)-local automaton is a subautomaton of a complete irreducible (λ, ρ)-local automaton (see Example 6).

The proof of Proposition 9 uses the following statement.

Proposition 10 Let A 1 and A 2 be automata such that A 2 is obtained from A 1 by input (or output) merge. If A 1 is a subautomaton of a local automaton B 1 , then the Nasu embedding of A 2 with respect to A 1 and B 1 , is a local automaton with the same order as B 1 .

Proof We treat the case of an input merge. The case of an output merge is symmetrical.

Let R, S be the matrices defined as in the proof of Proposition 1. The transition matrix of A 1 is equal to RS while the transition matrix of A 2 is equal to SR. We have a ∈ S p,q if (p, a, q) ∈ E 1 and R p, p = 1. The additional S-edges are the triples (f, a, q) such that f = (p, a, q) is in F . The additional R-edges are the triples (p, 1, f ) such that f begins with p. An example of this construction is described in Figure 3.

Let π be the map defined on the set P of paths of B 1 of length at least 2 onto the set of nonempty paths of B 2 as follows. If (e 0 , e 1 , . . . , e n ) ∈ P with e i = (q i , a i , q i+1 ), we define π(e 0 , e 1 , . . . , e n ) = (g 0 , g 1 , . . . , g n-1 ) with g i = (p i , a i , p i+1 ) defined by p i = qi if e i ∈ E 1 and p i = e i if e i ∈ F .

We claim that π is a surjective map from the set P onto the set of nonempty paths of B 2 . We have to verify that each g i is an edge of B 2 . We distinguish four cases. (i) If p i , p i+1 ∈ P 2 . Then g i is an edge of A 2 and thus of B 2 . It is the concatenation of an S-edge and an R-edge.

(ii) If p i ∈ P 2 and p i+1 ∈ F . Then p i = qi and p i+1 = e i+1 . Thus g i is the concatenation of an S-edge and an ( R -R)-edge.

(iii) If p i , p i+1 are in F , then p i = e i and p i+1 = e i+1 . Thus g i = (p i , a i , p i+1 ) is the concatenation of an ( S -S)-edge and an ( R -R)-edge.

(iv) If p i ∈ F and p i+1 ∈ P 2 then p i = e i . Thus g i is the concatenation of an ( S -S)-edge and an R-edge.

Thus π is well defined. Moreover, one can verify that for any nonempty path c in B 2 there exists c ′ ∈ P such that π(c ′ ) = c. Thus π is surjective.

Let n be the order of B 1 . Let c = p w → q and c ′ = p ′ w → q ′ be two paths in


Serge Midonnet

Damien Masson

R Émi Lassalle

Slack Time Computation for Temporal Robustness in Embedded Systems

Keywords: Slack Time, Robustness, LejosRT. ✦

We propose to handle execution duration overruns (temporal faults) in real-time embedded systems. When a temporal fault occurs, the slack time can be dynamically determined and assigned to the faulty task in order to complete its treatment. This mechanism improves the temporal robustness of real-time systems. We demonstrate that an approximate slack stealer algorithm like the MASS algorithm is a good solution for real-time embedded systems. We validate the feasibility of this approach by an implementation on the Lego Mindstorm NXT platform.

PROBLEM DESCRIPTION

The constraints in a hard real-time system are defined such that no deadlines of any task are missed. Moreover, the worst case execution time (WCET) of a task is estimated or computed in order to ensure that the task never runs for a duration longer than its WCET. But this determination is very difficult to achieve.

If a task overruns its WCET, the system may fail unless this WCET overrun does not cause any deadline misses. We need to detect and isolate temporal faults to protect the system against faulty tasks.

Without this protection, known as fault isolation, it is impossible to build robust real-time applications. The problem is to know how long a periodic real-time task can exceed its WCET without violation of the fault isolation property.

In section 3 we briefly present a static solution which consists of the determination of the allowance, a value we can add to the WCET of each task.

The drawback of this approach is that it provides a very pessimistic value because it is calculated in the worst case. The approach we propose in section 4 is to use a dynamic value called the slack time. This approach also has the advantage to collect gain time, ie the time freed in the system by a task completing before its WCET.

The rest of this paper is organized as follows: Section 2 presents our task model and assumptions. Section 3 introduces the concept of allowance to increase robustness in real-time systems and related works. Section 4 explains the slack time computation algorithms used in this work. Section 5 describes the target platform we used. We expose in Section 6 experimental results on comparative overhead measurement for DASS and MASS implementations on lejosRT. Finally we propose in Section 7 a proof of the concept based on three scenarios executed.

ASSUMPTIONS AND TASK MODEL

In this paper, we consider an application built from a set of n periodic real-time tasks {τ 1 , τ 2 , . . . , τ n }. Each task τ i is characterized by a period T i , a worst-case execution time C i and a relative deadline D i . We consider a staticpriority scheduling on a single processor. We assume that tasks are indexed by decreasing priority.

STATIC ALLOWANCE FOR ROBUSTNESS

One of the available approaches to increase the WCET of a task with respect of the fault isolation property is to compute a value denoted Allowance by Bougueroua et al. [START_REF] Bougueroua | Temporal robustness of real-time architectures specified by estimated wcets[END_REF]. The Allowance is the duration which can be added to the WCET of a task such that all tasks meet their deadlines. A first approach is to compute the Allowance from the WCRT. For a given value of allowance A i , this method consists of checking that the system remains schedulable when the execution duration of task τ i is equal to C ′ i = C i + A i . The maximal value for A i is found by a binary search.

Another approach to compute the allowance on the execution duration is the sensitivity analysis. This approach has been introduced by Bini et al. [START_REF] Bini | Sensitivity analysis for fixed-priority real-time systems[END_REF]. It is interesting as it is non recursive feasibility condition. The authors propose to consider the system only at time corresponding to the activation time of the highest priority tasks.

Both approaches provide the optimal value of the allowance value but their complexities are too high to be used [START_REF] Fauberteau | A robust partitioned scheduling for real-time multiprocessor systems[END_REF] online.

SLACK STEALING FOR ROBUSTNESS

Slack stealer algorithms was introduced in [START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks fixed priority preemptive systems[END_REF] in order to address the problem of jointly scheduling hard periodic tasks and soft aperiodic events. The general idea is to compute at a time instant t where there is an aperiodic pending request, for each hard real-time task, a value, called the slack. This value corresponds to the amount of time the task can suspend its execution without missing its deadline. Then a time interval equal to the minimum among these values can be used to handle aperiodic traffic, or in our work to let a task commit a temporal fault.

The first proposed approach to compute slack time was based on a table generated off line. This solution suffers to a big memory complexity issue due to the static table storage. So a dynamic exact approach (DSS) was proposed in [START_REF] Davis | Scheduling slack time in fixed priority pre-emptive systems[END_REF], and a dynamic approximate one to address the time complexity issue of the exact approach was proposed in [START_REF] Davis | On exploiting spare capacity in hard real-time systems[END_REF]. This dynamic approximation relies on the computation of a lower bound on the slack values and is called Dynamic Approximate Slack Stealer (DASS).

We proposed in [START_REF] Masson | Userland Approximate Slack Stealer with Low Time Complexity[END_REF] the Minimal Approximate Slack Stealer (MASS) algorithm. This algorithm also computes a lower bound on the slack values. The time complexity and the overhead of this algorithm are lower than the DASS ones, but this is at the expense of losing precision on the computed lower bound. However we demonstrated through extensive simulations that the loss of precision against DASS was negligible.

Dynamic Slack Stealing (DSS)

The algorithm relies on the determination at time t and for each priority level of the available slack time, S i (t), also denoted as the i-level laxity. It represents the maximum amount of time the task τ i can be delayed without missing its deadline. This value is equal to the number of unused time units at priorities higher or equal to i between t and the next τ i deadline. The length of this interval is noted d i (t).

The number of "stealable" time units in the system, the system laxity, is the minimum value among the i-level laxities : S(t) = min ∀i S i (t).

To compute the S i (t) values, the interval between t and the next τ i deadline that we denote [t, t + d i (t)) is viewed as a succession of i-level busy periods 1 and ilevel idle periods 2 . Then, S i (t) is the sum of the i-level idle period lengths.

Equations to compute respectively the end of a busy period starting at time t and the length of an idle period starting at time t can be derived from the feasibility analysis theory [START_REF] Audsley | Applying new scheduling theory to static priority pre-emptive scheduling[END_REF]. These two equations are then recursively applied until the reach of the next deadline to determine S i (t).

1. periods where the processor is servicing priorities higher or equal to i 2. processor idle periods or periods where processor serves priorities lower than i Assuming that there is a time t where the S i (t) was up to date for all tasks, it is possible to compute S i (t ′ ) as follow:

1) if none of the periodic hard real-time tasks ends in [t, t ′ ) a) if the processor is idle or executing soft aperiodic requests

∀j : S j (t ′ ) = S j (t) -(t -t ′ ) (1)
b) if the processor is executing hard periodic task

τ i ∀j < i : S j (t ′ ) = S j (t) -(t -t ′ ) (2)
2) if hard real-time task τ i ends at time t ′′ ∈ [t, t ′ ), S i (t ′′ ) has to be computed using the recursive analysis described at the beginning of this section. This algorithm is not directly usable because of the time complexity of the recursive computation of the S i (t) to perform at each task ends. However, this part can be replaced by the computation of a lower bound.

Dynamic Approximate Slack Stealer (DASS)

Since S i (t) is the sum of the i-level idle period lengths in the interval [t, t + d i (t)), [START_REF] Davis | On exploiting spare capacity in hard real-time systems[END_REF] proposes to estimate this quantity by computing a bound on the maximal interference the task τ i can suffer in this interval. A bound on this interference is given by the sum of the interferences from each task with a higher priority than τ i . Then Equation 3 3 gives the interference suffered by a task τ j from a task τ i in an interval [a, b].

I j i (a, b) = c i (t)+f i (a, b)C i + min(C i , (b -x i (a) -f i (a, b)T i ) 0 ) (3)
Where c i (t) is the remaining cost of current instance of task τ i at time t.

The function f i (a, b) returns the τ i instance number which can begins and completes in [a, b]. It is given by Equation 4.

f i (a, b) = b -x i (a) T i 0 (4)
The function x i (t) represents the first activation of τ i which follows t. Then the interference is composed by the remaining computation time needed to complete the current pending request, by a number of entire invocations given by f i (a, b), and by a last partial request.

A lower bound on the S i (t) value is given by the length of the interval minus the sum of the interferences from each task with a higher or equal priority than τ i . It is recapitulated by Equation 5.

S i (t) =   d i (t) -t - ∀j≤i I i j (t, d i (t))   0 (5)
3. the notation (x) 0 means max(x, 0)

We can then implement DASS by adding in the scheduler the following operations at the start and end of each periodic instance (dt refers to the elapsed time since the last start or end of a periodic task):

• Beginning of periodic task τ k : let l be the priority level of the system before the activation of τ k . We have ∀i < l, S i (t) = S i (t ′ )dt

• End of periodic task τ k :

∀i < k, S i (t) = S i (t ′ ) -dt (7) S k (t) =   d k (t) -t - ∀j≤k I k j (t, d k (t))   0 ( 8
)

Minimal Approximate Slack Stealer (MASS)

In order to reduce the complexity and the overhead of the added operations, we decompose the maximum available slack per task (S i (t)) into two different pieces of data: first wi (t), the maximum possible work at priority i regardless of lower priority processes ; second ci (t), the effective hard real-time work to process at the instant t at priority i, ie task τ i remaining cost. We then have S i (t) = wi (t) -ci (t).

Then, wi value only have to be updated at the end of periodic instances. Moreover, they are not recomputed from scratch, but the computation is incremental. This permits to always compute the interferences on a time interval equal to the task period, which can be performed in constant time. However, we still have to maintain the ci values at each preemption. We denote the time between two periodic task ends by dt f and then time between two periodic task begins by dt b .

1) End of periodic task τ k .

∀i < k, wi (t) = wi (t f ) -dt f ∀i > k, wi (t) = wi (t f ) -dt f + ci i = k, wi (t) = wi (t f ) -dt f + T i -I i (t) ci (t) = C i (9) 2) Beginning of a periodic task preempting τ k . ck (t) = ck (max(t f , t d )) -min(dt f , dt d ) (10)

LEJOSRT

Lego Mindstorms NXT is a programmable robotics kit released by Lego in late July 2006. The main component in the kit is a brick-shaped computer called the NXT Intelligent Brick. It can take input from up to four sensors and control up to three motors. In addition, a lot of custom sensors e.g. gyro, compass, color detector, movement detector, temperature detector, using a wide range of technologies, analog, digital can be used. LeJOS NXJ is an open source alternative firmware for the brick that implements a Java Virtual Machine. We forked the Lejos Project to the LejosRT project to introduce a subset of the Real-Time Specification for Java (RTSJ) [START_REF]The real-time specification for java (RTSJ)[END_REF]. We use this platform available on-line on sourceforge as a validation target for this work.

COMPARATIVE OVERHEADS DASS/MASS ON LEJOSRT

We present in this section an overhead comparison of DASS and MASS implementations on lejosRT.

A main issue is to obtain an accurate time measure on the system. We chose to modify the virtual machine in order to perform a time measure when the first thread starts and another one when a thread ends a periodic instance.

Experience description

We consider a program with n real-time threads with the same release parameters (period and deadline) but with n different priorities. Moreover we shift start times in order to start first the thread with the lowest priority and last the one with the highest priority. That permits to maximize the number of preemptions. The period of the thread with the lowest priority is set shorter than the other one in order to have this thread preempted twice be each other ones. We measure the needed time to execute two instances for each thread. The system load is then maximal (100%).

Experimental results

Fig. 1. System overheads with DASS and MASS depending on task number (in ms)

Figure 1 presents the results obtained for a range of thread number from 2 to 25. Each test was performed ten times and the values reported in Y axis are the average differences between the time execution of the program on LejosRT without any slack computation and with the concerned algorithm (respectively DASS and MASS). On the X axis is reported the number of thread.

We can note that the MASS overhead is always lower than the DASS one. This was the expected result, that this experiment confirmed on real implementations. Moreover, the more threads we have, the higher the measured difference is. There is an exception with 5 and 10 tasks where the MASS overhead is negligible in regards to the overheads of the scheduling algorithm on the virtual machine.

PROOF OF CONCEPT : EXECUTIONS TRACES

Three scenarios are presented here. On the following figures, the gray zones represent cost overruns. The times are in milliseconds. The system is composed by 3 periodic tasks which are synchronously activated. The task with the higher priority performs an infinite loop, and so will obviously overrun its cost. We can see that the mechanism succeed in letting it execute as long as possible. The two other tasks respect their deadlines. This time, both task τ 1 and τ 3 overrun their cost. Moreover, we shifted the task activations to observe a preemption during the slack time utilization. So τ 3 starts first, overruns its cost, but continue its execution since there is laxity in the system. It is preempted by τ 2 which is preempted in turn by τ 1 . τ 1 overruns its cost and consumes a part of the system laxity. Finally τ 1 ends its execution, τ 2 can resume and complete, and τ 3 consumes the rest of the laxity.

One task commits a cost overrun

Two tasks commit cost overrun

Gain time collection

This last experiment is quite the same as the previous, except we make τ 2 finish before its WCET. We can see that the gain time generated is automatically collected by MASS in the system laxity. That permits τ 3 to ends before its deadline.

CONCLUSION

We have proposed an approximate slack stealing algorithm (MASS) and we prove in this paper its usability to enforce the robustness of real-time systems. We demonstrate that this mechanism has a lower overhead than the other existing algorithm: DASS, which is a researched quality since we want to deal with cost overruns. Indeed, the lower computation time the mechanism takes, the more time to handle the cost overrun we have. Finally, we implemented it and evaluated its behavior in the presence of temporal faults on a real embedded platform (LejosRT).

•

  D. Masson and S. Midonnet are with the Paris-Est university and the "Laboratoire d'informatique Gaspard-Monge" (UMR CNRS 8049 LIGM). • D. Masson is also affiliated to ESIEE Paris. • Rémi Lassalle is Capitaine in the french Nationale Gendarmerie and a second year student of the Ecole Nationale Supérieure de Techniques Avancées (ENSTA).

Fig. 2 .

 2 Fig. 2. Consumption of all the available laxity by one thread

Fig. 3 .

 3 Fig. 3. Consumption of the available laxity by two threads

Fig. 4 .

 4 Fig. 4. Example with gain time


Guillaume Blin
email: gblin@univ-mlv.fr

Maxime Crochemore
email: maxime.crochemore@univ-mlv.fr

Sylvie Hamel
email: sylvie.hamel@umontreal.ca

Stéphane Vialette
email: vialette@univ-mlv.fr

Median of an odd number of permutations

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The problem of finding the median of a set of m permutations of [n] under the Kendallτ distance is best known in the literature as the Kemeny Score Problem : given m voters and a list of n candidates that they have to order according to their preference, the problem consist in finding a Kemeny consensus. A Kemeny consensus is an order of the candidates that agrees the most with the order of the m voters, i.e., that minimizes the sum of the disagreements. This problem has been proved to be NPcomplete when m ≥ 4 [START_REF] Dwork | Rank Aggregation Methods for the Web[END_REF] (the complexity is unknown for m = 3 and polynomial-time solvable for m = 2) and some approximation algorithms have been derived. First, a randomized algorithm with approximation factor 11/7 [START_REF] Ailon | Aggregating inconsistent information: Ranking and clustering[END_REF] and then a deterministic one with approximation factor 8/5 [START_REF] Williamson | Deterministic algorithms for rank aggregation and other ranking and clustering problems[END_REF] were designed. In 2007, a PTAS result has been obtained [START_REF] Kenyon-Mathieu | How to rank with few errors[END_REF] and a year later, some fixed-parameter algorithms have been described [START_REF] Betzler | Fixed-Parameter Algorithms for Kemeny Scores[END_REF]. In a previous article, we focused on the open case where m = 3 and derived some nice combinatorial properties of the medians [START_REF] Blin | Finding the median of three permutations under the Kendall-τ distance[END_REF]. In this contribution, we generalize those results and derive new ones for the general case of finding the medians of m permutations, where m is odd. This article is organized as follow. After introducing the basic definitions and notations (in Section 2), we provide, in Section 3, some combinatorial properties of the medians which allow us to reduce the search space of the brute force algorithm. Finally, in sections 4 and 5, we provide our heuristics, the results and some future works respectively.

Definitions and notations

A permutation π is a bijection of [n] = {1, 2 . . . , n} onto itself. The set of all permutations of [n] is denoted S n . As usual, we denote a permutation π of [n] as π = π 1 π 2 . . . π n . The identity permutation corresponds to the identity bijection of [n] and is denoted ı = 12 . . . n. The inverse permutation of π, denoted π

-1 = π -1 1 . . . π -1 n , is the permutation such that π • π -1 = π -1 • π = ı
, where • represents the composition of functions (e.g. π = 25431, π -1 = 51432). In other words, π -1 i denotes the position of integer i in the permutation π. The cardinality of a set S is denoted #S. A pair (π i , π j ) of elements of the permutation π is called an inversion if π i > π j and i < j. The number of inversions of a permutation π is denoted inv(π). Let us remark that, since the inversions are generators of S n , we can view S n with these generators as a Coxeter group. In this context, the number of inversions of a permutation π is called the length of π and is denoted by ℓ(π). See Chapter 5 of [START_REF] Humphreys | Reflection Groups and Coxeter Groups[END_REF] for more details. The Kendall-τ distance, denoted d KT , counts the number of pairwise disagreements between two permutations and can be defined formally as follows: for permutations π and σ of [n], we have that

d KT (π, σ) = #{(i, j) | i < j and [(π -1 i < π -1 j and σ -1 i > σ -1 j ) or (π -1 i > π -1 j and σ -1 i < σ -1 j )]
}. Note that we can easily compute inv(π) as inv(π) = inv(π -1 ) = d KT (π, ı). Given any set of permutations A ⊆ S n and a permutation π, we have

d KT (π, A) = σ∈A d KT (π, σ).
The problem of finding a median of a set of permutations under the Kendallτ distance can be stated formally as follow:

Given A ⊆ S n , we want to find a permutation π * of [n] such that d KT (π * , A) ≤ d KT (π, A), for all π ∈ S n .
In order to represent the disagreements between pairs of elements in a permutation π with respect to the permutations in A ⊆ S n , we introduce hereafter the notion of disagreements graph.

Definition 1

We call the disagreements graph of π = π 1 π 2 . . . π n with respect to a set A ⊆ S n , denoted G(π, A), the graph obtained from π by considering each π i as a node and by drawing weighted edges between each pair of nodes (π i , π j ), with i < j. The weight of an edge (π i , π j ), denoted w G(π,A) (π i , π j ), represents the number of order disagreements of this pair of elements in π with the same pair in each permutation of the set A, i.e., the distance contribution of this pair in d KT (π, A). With this definition, we have that

d KT (π, A) = (π i ,π j ) i<j w G(π,A) (π i , π j ).
Example 1 Let π = 4213 and A = {π 1 , π 2 , π 3 }, where π 1 = 2134, π 2 = 2413 and π 3 = 4123. Then, the disagreements graph of π with respect to A, i.e. G(π, A) is given in Figure 1.

Reducing the search space

When dealing with permutations, searching through the whole set of permutations [n] quickly becomes impossible since there are n! such permutations. To be able to compare our heuristics with the brute force algorithm for permutations of [n] where n > 12, we need to reduce the search space so that the computation will take place in a reasonable time. Here, given a set of permutations A ⊆ S n , with #A = m, we derive some combinatorial properties on medians which will considerably reduce the search space by discarding unrelevant permutations.

In order to derive such properties for any median π * of a set A ⊆ S n , let us consider the properties of its disagreements graph G(π * , A). We first provide boundaries on the weight of edges of G(π * , A) (Theorems 1 and 2).

Theorem 1 Let π * = π * 1 . . . π * n be a median of a set of permutations A ⊆ S n under the Kendall-τ distance and let m = #A. Then, for 1 ≤ i ≤ n -1, w G(π * ,A) (π * i , π * i+1 ) ≤ ⌊ m 2 ⌋.
Proof. By contradiction, let us assume that, given π * , there exist an 1

≤ i ≤ n -1 s.t. w G(π * ,A) (π * i , π * i+1 ) = k > ⌊ m 2 ⌋. Let π * * = π * 1 . . . π * i-1 π * i+1 π * i π * i+2 .
. . π * n be the resulting permutation of the transposition of the elements in positions i and i + 1 in π * . Considering π * and π * * , the order of any element of [n]\{π * i , π * i+1 } and π * i or π * i+1 is the same. The only difference concerns the relative order between π * i and π * i+1 . Thus, all the edges of G(π * , A) have the same weights than those of G(π * * , A) except the one between π * i and

π * i+1 . More precisely, since w G(π * ,A) (π * i , π * i+1 ) = k, there are k permutations over the m permutations of A in which π * i+1 precedes π * i . Since in π * * , π * i and π * i+1 have been transposed, w G(π * * ,A) (π * * i , π * * i+1 ) = m -k. Since, by hypothesis, k > ⌊ m 2 ⌋, we have that m -k < k and thus, d KT (π * * , A) = (π * * i ,π * * j ) i<j w G(π * * ,A) (π * * i , π * * j ) < d KT (π * , A)
In other words, π * is not, by definition, a median ; a contradiction.

Theorem 2 Let π * = π * 1 .
. . π * n be a median of a set of permutations A ⊆ S n under the Kendall-τ distance and let m = #A. Then the maximal weight of edges in

G(π * , A) is m -1.
Proof. By contradiction, let us assume that, given a median

π * = π * 1 . . . π * n of a set A = {π 1 , . . . , π m } s.t. m = #A, there exist 1 ≤ i < j ≤ n s.t. w G(π * ,A) (π * i , π * j ) = m.
Let π * * be the resulting permutation of the exchange of the elements in positions i and j in π * . Considering the weights of the edges of G(π * , A) and G(π * * , A), the only differences concern the edges (π Let us first prove a nice property on G(π * , A) : namely that ∀i

* i , π * k ), i + 1 ≤ k ≤ j and (π * k , π * j ), i + 1 ≤ k ≤ j -1 (See Figure 2). π * 1 π * i π * i+1 π * j-1 π * j π * n w(π * i , π * i+1 ) w(π * j-1 , π * j ) m • • • • • • • • • G(π * , A): w(π * i , π * j-1 ) w(π * i+1 , π * j ) π * 1 π * j π * i+1 π * j-1 π * i π * n w(π * j , π * i+1 ) w(π * j-1 , π * i ) 0 • • • • • • • • • G(π * * , A): w(π * j , π * j-1 ) w(π * i+1 , π * i )
+ 1 ≤ k ≤ j -1, w G(π * ,A) (π * k , π * j ) ≥ m-w G(π * ,A) (π * i , π * k ). First, note that, since w G(π * ,A) (π * i , π * j ) = m, in all the permutations of A π * j precedes π * i . Consider now any ∀i + 1 ≤ k ≤ j -1.
By definition, there are m -w G(π * ,A) (π * i , π * k ) permutations of A in which π * k appears after π * i and thus after π * j . Consequently,

w G(π * ,A) (π * k , π * j ) ≥ m -w G(π * ,A) (π * i , π * k ). Let us now compare d KT (π * , A) and d KT (π * * , A). By construction, as mentionned above, d KT (π * , A)-d KT (π * * , A) = (m+ j-1 k=i+1 w G(π * ,A) (π * i , π * k )+w G(π * ,A) (π * k , π * j ))- (0 + j-1 k=i+1 w G(π * * ,A) (π * * j , π * * k ) + w G(π * * ,A) (π * * k , π * * i )). Note that, since j-1 k=i+1 w G(π * * ,A) (π * * j , π * * k ) + w G(π * * ,A) (π * * k , π * * i )) = j-1 k=i+1 (m - w G(π * ,A) (π * i , π * k )) + (m -w G(π * ,A) (π * k , π * j ))
, one may conclude that d KT (π * , A)d KT (π * * , A) > 0 and thus that π * is not a median; a contradiction. Theorem 2 states that there are no edges of weight m in G(π * , A), where m = #A. This means that if a pair of integers appears in the same order in all permutations of A then they have to appear in that order in any median π * of A. Note that this theorem, in an other form, has already been stated and proved in the area of applied finance and uses what they called an Extended Condorcet Criterion [START_REF] Truchon | An Extension of the Condorcet Criterion and Kemeny Orders[END_REF].

For A ⊆ S n , let inv(A) = σ∈A inv(σ).
The triangle inequality gives us a bound on the number of inversions in a median π * of A.

Theorem 3

inv(A) -d KT (π, A) m ≤ inv(π * ) ≤ inv(A) + d KT (π, A) m
where m = #A and where π is considered, w.l.o.g., to be the permutation in A that minimizes d KT (π, A).

Proof. It is easy to show that the Kendall-τ distance is indeed a distance in the mathematical sense of the term. That means, in particular, that it needs to satisfy the triangle inequality (∀x, y, z, permutations of [n], d KT (x, z) ≤ d KT (x, y) + d KT (y, z)).

Let A = {π 1 , . . . , π m }. By the triangle inequality we have that for all 1

≤ i ≤ m, inv(π * ) = d KT (π * , ı) ≤ d KT (π * , π i ) + d KT (π i , ı) = d KT (π * , π i ) + inv(π i ),
Summing these inequalities we get

m inv(π * ) ≤ m i=1 d KT (π * , π i ) + inv(π i ) = d KT (π * , A) + inv(A).
Now, since π * is the median of A with respect to the Kendall-τ distance we need to have that

d KT (π * , A) ≤ d KT (π i , A),
for all 1 ≤ i ≤ m. Choosing π to be the π i ∈ A that minimizes d KT (π, A), we have

m inv(π * ) ≤ d KT (π, A) + inv(A),
which gives us the first inequality. The second inequality is easily derived in the same manner from the following triangle inequalities, 1 ≤ i ≤ m:

inv(π i ) = d KT (π i , ı) ≤ d KT (π i , π * ) + d KT (π * , ı) = d KT (π i , π * ) + inv(π * ).
Theorem 3 gives upper and lower bounds (but not optimal ones) on the number of inversion in a median π * . This is interesting since there exist a CAT-algorithm that computes all the permutations of [n] having exactly k inversions [START_REF] Effler | A CAT algorithm for generating permutations with a fixed number of inversions[END_REF]. This Theorem thus reduces the search space for a median while Theorem 1 and 2 gives us a set of constraints that a median should satisfy.

Our heuristics

The idea of our heuristics is to apply a series of "good" cyclic movements on the permutations in A, in order to make them closer to a median. Our heuristics only works with sets of permutations of odd cardinality (see Theorem 4). Formally we have the following definitions and algorithm.

Definition 2 Given π = π 1 . . . π n , we call cyclic movement of a segment π[i..j] of π, denoted c[i, j](π), the cycling shifting of one position to the right (c r [i, j]) or to the left (c ℓ [i, j]) of the segment inside the permutation π:

c r [i, j](π) = π 1 . . . π i-1 π j π i . . . π j-1 π j+1 . . . π n , c ℓ [i, j](π) = π 1 . . . π i-1 π i+1 . . . π j π i π j+1 . . .

π n

When j = i + 1, a cyclic movement corresponds to a transposition. Definition 3 Given a set of permutations A ⊆ S n , we will say that a cyclic movement is a k-move if

d KT (c[i, j](π), A) = d KT (π, A) + k. Definition 4 A good cyclic movement c[i, j] is a k-move, where k < 0.
This means that if we apply a good cyclic movement to π we obtain a permutation that is closer to a median than π, i.e., we have d KT (c[i, j](π), A) < d KT (π, A). Theorem 4 gives us a way to easily find these good moves (in fact any k-move) on a starting permutation π.

Theorem 4 Let A ⊆ S n , be a set of permutations, with #A = m, m odd. Let π be a permutation from which we want to derive π * , a median of A with respect to the Kendall-τ distance. We have that c

r [i, j](π) (resp. c ℓ [i, j](π)) is a k-move, k ∈ Z, iff j -i ≡ k mod 2 and j-1 t=i w G(π,A) (π t , π j ) resp. j t=i+1 w G(π,A) (π i , π t ) = m(j -i) -k 2 .
Proof. (⇒) If c[i, j](π) is a k-move (to the right or left) then, by definition

d KT (c[i, j](π), A) = d KT (π, A) + k. ( 1
)
Between the two disagreements graphs G(π, A) and

G(c r [i, j](π), A) (resp. G(π, A) and G(c ℓ [i, j](π), A)) only the edges (π t , π j ), i ≤ t ≤ j -1 (resp. (π i , π t ), i + 1 ≤ t ≤ j)
change weights. So, there are j -i edges that change weights and their new weights are equals to m minus their old weights. Let x p be the number of those edges that have weight p in G(π, A), we have

m p=0 x p = j -i (2)
and Equation 1gives us that

m p=0 (m -p)x p = m p=0 p x p + k (3)
that can be written has

m p=0 (m -2p)x p = k (4)
Subtracting Equation 2from Equation 4we finally get

m p=0 (m -2p -1)x p = k -(j -i) (5)
which gives us that k -(j -i) has to be even (since m is odd) and so j -i ≡ k mod 2. Now to prove the second part of this implication, we have

j-1 t=i w G(π,A) (π t , π j ) resp. j t=i+1 w G(π,A) (π i , π t ) = m p=0 p x p = m m p=0 x p - m p=0 (m -2p)x p 2 (2) = m(j -i) - m p=0 (m -2p)x p 2 (4) = m(j -i) -k 2 .
(⇐) We have to prove that if a) j -i ≡ k mod 2 and b)

j-1 t=i w G(π,A) (π t , π j ) resp. j t=i+1 w G(π,A) (π i , π t ) = m(j-i)-k 2 then c r [i, j](π) (resp. c ℓ [i, j](π)) is a k- move, k ∈ Z (i.
e. Equation 3 holds). Taking the same notation as before for

x p , 0 ≤ p ≤ m, b) implies that m p=0 p x p = m(j -i) -k 2 (6)
We want to show that Equation 3 holds i.e that both parts of the equation are equals.

The right part of Equation 3 is

m p=0 p x p + k (6) = m(j -i) -k 2 + k = m(j -i) + k 2
We show now that the left part of Equation 3 is also equals to m(j-i)+k

2 : m p=0 (m -p) x p = m m p=0 x p - m p=0 p x p (2)et(6) = m(j -i) - m(j -i) -k 2 = m(j -i) + k 2
It is now time to present our heuristics whose pseudo-code is depicted in Figure 3.

The idea is to begin our search for the median in any permutation π ℓ ∈ A, 1 ≤ ℓ ≤ m, and to apply good cyclic movements to this starting point till there is no more possible good movement. We apply m times our pseudo-code, with π = π ℓ , 1 ≤ ℓ ≤ m and our "median" is the best result we obtain from these m runs.

Algorithm FindMedian (π, A) n ← length(π) bool ← 0 (will be changed to 1 if there is no more possible "good" movement) chang ← 0 (will tell us if some movements were made) We tested this heuristics on 2000 random sets A of permutations of [n] for 6 ≤ n ≤ 11, for the different cardinalities #A = 3, 5, 7 and 9 (For bigger n, it was too long to get the real medians with the brute force algorithm). Table 4 shows the percentage of errors of our heuristics on these runs. This percentage decreases when the cardinality of A increases from 3 to 9, since a bigger cardinality means more starting points for our heuristics. It is worth to mention that when our heuristics could not find the real median π * in these runs, the difference between the Kendall-τ distance of the permutation found by our heuristics and π * was always one. Considering 0-moves When our heuristics does not find the median π * , it means that we are stuck in a local minimum and there is no more possible good cyclic movement that we can make. We decided in this case to apply a fixed number of 0-moves in hope that these moves will help us go out of the local minimum. Given a permutation π, we can easily find these 0-moves with Theorem 4. Among these 0-moves, if at least one has the property described in Theorem 5 we are guaranteed to move out of the local minimum. So, the 0-moves with this properties will be call "good".

WHILE bool <> 1 DO FOR i from 1 to n -1 DO FOR j from i + 1 to n DO IF c r [i, j](π) or c ℓ [i, j](π) is a good movement THEN π ← c good [i, j](π) chang ← chang +1 END IF END FOR END FOR IF chang = 0 THEN bool ← 1 END IF END WHILE RETURN π
Theorem 5 Let π be the permutation found by our heuristics FindMedian as a candidate for a median π * of a set of permutations

A with #A = m, m odd. If c r [i, j](π) (resp. c ℓ [i, j](π)) is a 0-move and w G(π) (π i-1 , π j ) or w G(π) (π j-1 , π j+1 ) ≥ ⌈ m 2 ⌉ (resp. w G(π) (π i-1 , π i+1 ) or w G(π) (π i , π j+1 ) ≥ ⌈ m 2 ⌉ ), then there exist a good move (i.e a k-move, k < 0) in c r [i, j](π) (resp. c ℓ [i, j](π)).
Proof. This is easy to see since in c r [i, j](π) (resp. c ℓ [i, j](π)) the elements π i-1 , π j and π j-1 , π j+1 (resp. π i-1 , π i+1 and π i , π j+1 ) will become consecutive elements. Since the edges between these elements have weights ≥ ⌈ m 2 ⌉ and m is odd, the transposition We implemented a new heuristics "FindMedianZeroMoves(π,A)" that add to our previous heuristics the possibility to do a fixed number of 0-moves (good 0-moves or random ones). We tested this new heuristics on 20 000 randoms sets A of triplets of permutations of [n], 6 ≤ n ≤ 10, with 3 has the maximal number of 0-moves permitted. Table 3 shows our results. We see that on these examples we always got to a median of A and that in most of the cases, no 0-moves where needed to get to this median.

(π i-1 , π j ) or (π j-1 , π j+1 ) in G(c r [i, j](π), A) (resp. (π i-1 , π i+1 ) or (π i , π j+1 ) in G(c ℓ [i, j](π), A))

Future works

Since this article is a work in progress, there is still a lot of questions we need to answer. Stating only a few, we have the following ones: Can we find combinatorial properties that will completely describe the set of 0-moves that can make us move out of a local minimum? Are 0-moves enough to ensure that in all the cases, we can get out of local minimum? If not, a Monte Carlo approach could be a good probabilistic way to attack the problem.

We are also interested to investigate the number of medians of different sets A ⊆ S n . Some prelimary tests on sets of triplets of permutations show (see Table 4) that this number varies a lot (from 1 to 33 in our 2000 triplets of permutations of [START_REF] Truchon | An Extension of the Condorcet Criterion and Kemeny Orders[END_REF].) Can we find some combinatorial properties of A that indicates a small (resp. larger) number of medians? Also, it seems to be more probable for a set of permutations A to have a odd number of medians than an even one. Can we understand why? A possible direction to answer these questions could be to consider the Bruhat ordering of permutations; Maybe the position of the permutations of A in the Bruhat poset can help us understand the variation in the number of medians.

Figure 1 :

 1 Figure 1: Disagreements graph of π = 4213 with respect to A = {2134, 2413, 4123}. Here d KT (4213, A) = 5.

Figure 2 :

 2 Figure 2: Disagreements graphs of π * and π * *

Figure 3 :

 3 Figure 3: Pseudo-code of our heuristics FindMedian

Table 2 :

 2 Percentage of errors of our heuristics on 2000 sets A of permutations of [n], 6 ≤ n ≤ 12, where #A = m, m = 3, 5, 7, 9.

Table 3 :

 3 will then become a good move, i.e. a k-move, k < 0 Percentage of errors of the heuristics FindMedianZeroMoves on 20 000 sets A of triplets of permutations of [n], 6 ≤ n ≤ 10 and percentages of cases where k 0-moves were needed to get the median, 0 ≤ k ≤ 3.

Table 1 :

 1 Table1compares the computation time needed to find the medians of 3 permutations of [n], for 4 ≤ n ≤ 11, using 1) the brute force algorithm and 2) the brute force algorithm optimized by the results of Theorem 1 to 3. Running time, in seconds, of the brute force algorithm with and without the optimizations

	n	4	5	6	7	8	9	10	11
	time BF	0 0.0002 0.0005 0.0042	0.04	0.425	5.03	63.33
	time BFopt. 0	0	0.0002 0.0012 0.0064 0.0238 0.1496 1.0052

Table 4 :

 4 Percentages of medians for triplets of permutations of [n], 3 ≤ n ≤ 10

Acknowledgements

We thank Quentin Dejean, Anthony Estebe and Kelsey Lang who programmed all the algorithms and realized the tests as part of internship projects.

* partly supported by NSERC through an Individual Discovery Grant (Hamel)


Marie-Pierre Béal
email: beal@univ-mlv.fr

Mikhail V Berlinkov

Dominique Perrin
email: perrin@univ-mlv.fr

Marie-Pierre B Éal

A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA

Keywords: Černý's Conjecture, Road Coloring Problem, synchronized automata 2010 Mathematics Subject Classification: 68Q45, 68510, 68R15

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Synchronized automata are deterministic and complete finite-state automata admitting a synchronizing word, that is a word which takes each state of the automaton to a single special state. Černý conjecture claims that each n-state synchronized automaton has a synchronizing word of length at most (n -1) 2 [START_REF] Černý | homogénnym experimentom s konecnými automatmi[END_REF]. An extension of this conjecture due to Pin [START_REF] Pin | Le problème de la synchronisation et la conjecture de Černý[END_REF][START_REF]On two combinatorial problems arising from automata theory[END_REF] was shown to be false by Kari [START_REF] Kari | A counter example to a conjecture concerning synchronizing words in finite automata[END_REF]. The conjecture has been shown to be true for particular classes of automata like the class of circular automata by Dubuc [START_REF] Dubuc | Sur les automates circulaires et la conjecture de Černý[END_REF] (see also [START_REF]Sur un cas particulier de la conjecture de Černý[END_REF]). The linearisation of automata is used in [START_REF] Rystsov | Quasioptimal bound for the length of reset words for regular automata[END_REF] where a 2(n -1) 2 bound is optained for regular automata. A n(n -1)/2 upper bound has been obtained by Trahtman [START_REF] Trahtman | Synchronization of some DFA[END_REF][START_REF] Trahtman | Some aspects of synchronization of DFA[END_REF] for aperiodic automata. This upper bound was improved to n(n+1)/6 by Volkov [START_REF] Volkov | Synchronizing automata preserving a chain of partial orders[END_REF]. We refer to [START_REF]Synchronizing automata and the Černy conjecture[END_REF] for a recent beautiful thorough survey on synchronizing automata and Černý's conjecture.

In a previous note [START_REF] Béal | A note on Černý's conjecture and rational series[END_REF], the first author gave a proof of a quadratic bound for circular automata which is simpler than the one given in [START_REF] Dubuc | Sur les automates circulaires et la conjecture de Černý[END_REF]. Nevertheless, it does not allow one to get the tight (n -1) 2 bound. The proof uses rational series.

The formulation of the problem in terms of rational series is also used in [START_REF] Béal | A note on Černý's conjecture and rational series[END_REF] to provide a simple proof of a result from Kari [START_REF]Synchronizing finite automata on Eulerian digraphs[END_REF] which proves Černý's conjecture for automata with an underlying Eulerian graph.

Later, the result on circular automata was generalized by Carpi and d'Alessandro to a larger class called strongly transitive automata [START_REF] Carpi | The synchronization problem for strongly transitive automata[END_REF] and [START_REF]Strongly transitive automata and the Cerný conjecture[END_REF], see also [START_REF] Berlinkov | On Carpi and D'Alessandro conjecture[END_REF]. Their proof uses rational series as in [START_REF] Béal | A note on Černý's conjecture and rational series[END_REF]. They use the same methods to generalize the result of Kari to unambiguous automata. Carpi and D'Alessandro investigated the synchronization problem for the class locally strongly transitive deterministic automata in [START_REF]The synchronization problem for locally strongly transitive automata[END_REF].

In this paper, we prove the existence of a quadratic upper bound for the length of a synchronizing word for a class of finite automata called one-cluster. This means that, for some letter a, there is only one cycle with all edges labeled by a. The proof is an extension of the argument of [START_REF] Béal | A note on Černý's conjecture and rational series[END_REF] and uses again rational series. We here slightly improve the upper bound on the size of a shortest synchronizing word obtained in [START_REF]A quadratic upper bound on the size of a synchronizing word in one-cluster automata[END_REF] from 2n 2 -6n + 5 to 2n 2 -7n + 7.

The class of one-cluster automata contains in particular the automata associated with finite prefix codes. We thus obtain the existence of a quadratic bound on the length of a synchronizing word for a finite maximal synchronized prefix code. This applies in particular to Huffman codes.

Let us mention two recent results connected to our work (we thank Hugo Vaccaro for pointing out these references to us). First, it is proved in [START_REF] Freiling | Almost all complete binary prefix codes have a self-synchronizing string[END_REF] that almost all finite maximal prefix codes are synchronizing. Next, in [START_REF] Biskup | Shortest synchronizing strings for Huffman codes[END_REF], it is proved that a finite maximal synchronized prefix code with n codewords of maximal length h has a synchronizing word of length O(nh log n). This bound is not comparable with ours. Indeed, since log

n ≤ h ≤ n -1, one has n(log n) 2 ≤ nh log n ≤ n 2 log n.
A preliminary version of this paper appeared in [START_REF]A quadratic upper bound on the size of a synchronizing word in one-cluster automata[END_REF].

Automata and series

Let A be a finite alphabet and A * be the set of finite words drawn from the alphabet A, the empty word ǫ included. A (finite) automaton A over some (finite) alphabet A is composed of a finite set Q of states and a finite set E of edges which are triples (p, a, q) where p, q are states and a is a symbol from A called the label of the edge. Note that we do not specify a set of terminal states and that, for this reason, our automata are sometimes called semi-automata. An automaton is deterministic if, for each state p and each letter a, there is at most one edge starting in p and labeled with a. It is complete deterministic if, for each state p and each letter a, there is exactly one edge starting in p and labeled with a. This implies that, for each state p and each word w, there is exactly one path starting in p and labeled with w. We denote by p • w the state which is the end of this unique path.

An automaton is irreducible if its underlying graph is strongly connected.

A synchronizing word for a deterministic complete automaton is a word w such that for any states p, q, one has p • w = q • w. A synchronizing word is also called a reset sequence or a magic sequence, or also a homing word. An automaton which has a synchronizing word is called synchronized (see an example on the right part of Figure 1). Fig. 1. Two complete deterministic automata labeled on A = {a, b}. A thick plain edge is an edge labeled by a while a thin dashed edge is an edge labeled by b. The automaton on the left is not synchronized. The one on the right is synchronized; for instance, the word aaa is a synchronizing word.

Let A = (Q, E) be a complete deterministic automaton. For any word u ∈ A * , we denote by M u the transition matrix of the action of u on the states Q. It is defined by:

(M u ) pq = 1 if p • u = q, 0 otherwise.
Note that if u, v are two words, we have

M uv = M u M v .
We define the rank of a word u as the cardinality of Q • u. Note that since the automaton is complete deterministic, this rank is non null, and that a word is synchronizing if and only if his rank is 1.

A circular automaton is a deterministic complete automaton on the alphabet A such that there is a letter a of A which induces a circular permutation of the states, i.e. such that M a is a circular permutation matrix.

We shall consider the set of non commutative formal series with coefficients in a ring K (with K = Z or K = Q), which are applications from A * to K. If S is such a series, the image of a word u of A * by S is denoted by S, u and called the coefficient of u in S.

As an example, the series S on {a, b} * with coefficients in Z defined by S, u = |u| a -|u| b maps a word u ∈ {a, b} * to the difference between the number of occurrences of a and b in u. A series s is K-rational if it has a K-linear representation. Its rank on K is the minimal dimension of all its linear representations.

For example, the series S defined on {a, b} * by S, u = |u| a -|u| b is rational of rank 2. The triple (λ, µ, γ) defined by

λ = 1 0 , µ(a) = 1 1 0 1 , µ(b) = 1 -1 0 1 , γ = 1 0 is a Z-linear representation of S of dimension 2.
Černý's conjecture gives an upper bound on the size of a shortest synchronizing word in a synchronized automaton.

Conjecture 1 ( Černý 1964) A synchronized n-state deterministic complete automaton has a synchronizing word of length at most (n -1) 2 .

The conjecture was proved by Dubuc for circular automata.

Proposition 1 [START_REF] Dubuc | Sur les automates circulaires et la conjecture de Černý[END_REF]) A circular synchronized n-state deterministic complete automaton has a synchronizing word of size at most (n -1) 2 .

One-cluster automata

In the sequel A = (Q, E) denotes an n-state deterministic and complete automaton over an alphabet A. We fix a particular letter a ∈ A.

Let R be the subgraph of the graph of A made of the edges labeled by a. The graph R is a disjoint union of connected component called a-clusters. Since each state has exactly one outgoing edge in R, each a-cluster contains a unique cycle, called an a-cycle, with trees attached to the cycle at their root. For each state p of an a-cluster, we define the level of p as the distance between p and the root of the tree containing p. If p belongs to the cycle, its level is null. The level of the automaton is the maximal level of its states.

A one-cluster automaton with respect to a letter a is a complete deterministic automaton which has only one a-cluster. Equivalently, an automaton is one-cluster if it satisfies the following condition: for any pair of states p, q, one has p • a r = q • a s for some integers r, s.

Note that a one-cluster automaton whose level is null is circular.

Let C be a cycle of A and P be a subset of C. A word u is said to be Paugmenting if card(P u -1 ∩ C) > card(P ), where we denote P u

-1 = {q ∈ Q | q • u ∈ P }.
We now prove the existence of a quadratic upper bound on the size of a shortest synchronizing word in a synchronized automaton.

Let A be a synchronized n-state deterministic complete automaton. If A is onecluster, then it has a synchronizing word of length at most 2n 2 -7n + 7.

We prove the proposition for irreducible automata. The case of reducible automata easily reduces to this one. Let A = (Q, E) be a deterministic complete and irreducible n-state automaton. Since Černý's conjecture is proved for circular automata, we may assume that the level ℓ of the automaton is greater than or equal to 1.

Let C be the a-cycle and let m be the length of C. Let P be a subset of C. Note that a word u is a P -augmenting word if and only if

C M u P t > CP t ,
where P, C denote the characteristic row vectors of the sets P, C. Indeed,

C M u P t = r∈C,s∈P (M u ) rs = card{r ∈ C | r • u ∈ P } = card(P u -1 ∩ C).
Similarly, CP t = card(P ).

We denote by S the series defined by:

S, u = C M u P t -C P t ,
By definition, one has S, u > 0 if and only if u is a P -augmenting word.

Lemma 3. The series S has rank on Q at most n.

Proof. The series S is Z-rational since it is the difference of two Z-rational series (the second one is actually a constant). It has the following linear representation (λ, µ, γ) with λ ∈ Z 1×2n , µ :

A * → Z 2n×2n , λ ∈ Z 2n×1 , λ = (C, -C), µ(u) = M u 0 0 I , γ = P t P t ,
since S, u = λµ(u)γ. The rank of S on Q is bounded above by the dimension of the Q-vector space generated by the row vectors (CM u , -C). This space is included in the vector space generated by the vectors (CM u -C, 0) and the row vector (C, -C), where 0 is the null column vector of size n. Thus the rank of S is at most equal to the dimension of the vector space V generated by the vectors C(M u -I), plus one. We now show that the dimension of V is at most n -1. Since the automaton A is complete deterministic, for any u ∈ A * , M u 1 = 1, where 1 is the column vector with coefficients 1 of size n. This implies that C(M u -I) • 1 = 0. Thus the vectors of V are orthogonal to the vector 1. The dimension of V is thus at most n -1. This proves that the rank of S on Q is at most n.

We denote by T the Z-rational series defined by

T, u = S, ua ℓ ,
where ℓ denotes the level of the automaton A. If (λ, µ, γ) is a Q-linear representation of S of dimension n, then (λ, µ, µ(a ℓ )γ) is a representation of T . Thus the rank of T on Q is at most n.

Lemma 4. For any subset P of C such that P = ∅ and P = C, there is a Paugmenting word of length at most 2(n -1).

Proof. Since A is synchronized and irreducible, there is a synchronizing word u such that Q•u is a single state r belonging to P . Let k be a positive integer such that km ≥ ℓ, where m is the length of the cycle C. We have Q • ua km-ℓ a ℓ = r • a km = r. Hence ua km-ℓ a ℓ also is a synchronizing word focusing to r. Let R denote the characteristic row vector of r. Since q • u = r for all q ∈ Q and since C has m elements, we have CM u = mR. Moreover, since r ∈ C, RM a m = R. We have

T, ua km-ℓ = S, ua km = CM ua km P t -CP t = CM u M a km P t -CP t = mRM a km P t -CP t = mRP t -CP t = m -card(P ) = 0.
As a consequence T is non null. Since T has rank at most n on Q, there is a word v of length at most n -1 such that T, v = 0 (see [START_REF] Eilenberg | Automata, languages, and machines[END_REF] , [START_REF] Sakarovitch | Éléments de théorie des automates[END_REF] or [START_REF] Sakarovitch | Elements of automata theory[END_REF]).

If there is word v of length at most n -1 such that T, v > 0, then va ℓ is a P -augmenting word and the claim is proved. Otherwise, there is a word v of length at most n -1 such that T, v < 0.

Since ℓ is the level of A, the vector CM va ℓ is a linear combination of elements of C and the sum of its coefficients is equal to m.

We have

m-1 i=0 T, va i = m-1 i=0 S, va ℓ a i = m-1 i=0 C(M va ℓ a i -I)P t , = ( m-1 i=0 CM va ℓ M a i - m-1 i=0 C)P t , = (CM va ℓ ( m-1 i=0 M a i ) -mC)P t , = ( r∈C rM va ℓ m-1 i=0 M a i -mC)P t , = ( r∈C C -mC)P t = 0.
Indeed, for any r in C, the state q = r • va ℓ is in C and for any state q in C, the row of index q of the matrix m-1 i=0 M a i is the row vector C. As a consequence, there is a word w of length at most n + m -2 such that T, w > 0. Hence there is a P -augmenting word of length at most n + m -2 + ℓ.

Thus, in all cases, there is a word of length at most n + m -2 + ℓ which is P -augmenting.

To prove Proposition 2, we show that A has a synchronizing word of length at most 1 + 2m(n -2). Indeed, let P 1 be reduced to an arbitrary state of C.

If P 1 = C (that is to say if m = 1), then Q • a ℓ ⊆ P 1 ,
and thus a ℓ is a synchronizing word.

Otherwise, by Lemma 4, there exists a word u 1 of length at most n + m -2 + ℓ which is P 1 -augmenting. Set P 2 = P 1 u -1

1 ∩C. If P 2 = C, there is a word u 2 of length at most n + m -2 + ℓ which is P 2 -augmenting, and so on. In this way, we build a sequence u 1 , . . , u t-1 of words and a sequence P 1 , . . , P t of sets of states, with t ≤ m, such that, for 1 ≤ i < t,

• u i is a P i -augmenting word of length at most n + m -2 + ℓ;

• P i+1 = P i u -1 i ∩ C; • P t = C.
Then the word a ℓ u t-1 . . u 1 is a synchronizing word of length at most ℓ+(m-1)(n+ m-2+ℓ). Indeed,

Q•a ℓ u t-1 . . u 1 ⊆ C •u t-1 . . u 1 ⊆ P t-1 •u t-2 . . u 1 ⊆ . . P 2 •u 1 ⊆ P 1 .
Since m ≤ nℓ and m ≤ n -1, we have

ℓ + (m -1)(n + m + ℓ -2) ≤ ℓ + (m -1)(2n -2) ≤ n -m + 2mn -2n -2m + 2 ≤ 2mn -n -3m + 2 = (n -2)(2m -1) + m ≤ 1 + 2m(n -2) ≤ 1 + 2(n -1)(n -2) = 2n 2 -6n + 5.
We slightly improve this bound by giving a better upper bound on the size of the first augmenting word u 1 .

Let q be a state of C. We denote by R q the Z-rational series defined by

R q , u = S q , ua (n-m) ,
where S q , u = C M u q t -C q t and q is the row-characteristic vector of the state q.

The series R q has rank at most n. One can show, as for T , that R q is non null. If there a state q of C and a word u of length at most n-1 such that R q , u > 0, then ua (n-m) is a {q}-augmenting word of length 2n-m-1. Otherwise, R q , u ≤ 0 for any word u of length at most n -1 and any state q of C.

Let u ∈ A * of length at most n -1. q∈C R q , u = q∈C S q , ua (n-m) = q∈C (CM u M a (n-m) q t -Cq t ) = CM u M a (n-m) C t -C • C t = C • C t -C • C t = 0.
The last but one equality results from nm ≥ l which implies

CM u M a (n-m) = C.
As a consequence, R q , u = 0 for any state q of C. Since R q has rank at most n, R q is null, a contradiction. Thus there a state q of C and a word u of length at most n -1 such ua (n-m) is a {q}-augmenting word of length 2nm -1. Thus we get a {q}-augmenting word of length at most 2nm -1.

With this improvement, we obtain a synchronizing word of length at most ℓ

+ (2n -m -1) + (m -2)(n + m -2 + ℓ). We have ℓ + (2n -m -1) + (m -2)(n + m -2 + ℓ) ≤ n -m + 2n -m -1 + (m -2)(2n -2) ≤ n -m + 2n -m -1 + 2nm -4n -2m + 4 ≤ 2mn -n -4m + 3 = m(2n -4) -n + 3 ≤ (n -1)(2n -4) -n + 4 ≤ 2n 2 -7n + 7,
which completes the proof.

Application to finite prefix codes

In this section we show how the previous result can be applied to the automaton associated to a finite prefix code.

A prefix code on the alphabet A is a set X of words on A such that no element of X is a prefix of another word of X.

A prefix code is maximal if it is not contained in another prefix code on the same alphabet. As an equivalent definition, a prefix code X is maximal if for any word u in A * has a prefix in X or is a prefix of a word of X.

For a deterministic automaton A and an initial state i, the set X A of labels of first return paths from i to i is a prefix code. If the automaton is complete, the prefix code is maximal.

Conversely, for any finite prefix code X, there exists a deterministic automaton A such that X = X A . Moreover, the automaton A can be supposed to be irreducible. If X is a maximal prefix code, the automaton A is complete.

The automaton A can be chosen as follows. The set of states is the set Q of prefixes of the words of X. The transitions are defined for p ∈ Q and a ∈ A by p•a = pa if pa is a prefix of a word of X, and by p•a = ε if pa ∈ X. This automaton, denoted A X is a decoder of X. Let indeed α be a one-to-one map from a source alphabet B onto X. Let us add an output label to each edge of A X in the following way. The output label of (p, a, q) is ε if q = ε and is equal to α -1 (pa) if q = ε. With this definition, for any word x ∈ X * , the output label of the path i x -→ i is the word α -1 (x).

Let us show that, as a consequence of the fact that X is finite, the automaton A is additionally one-cluster with respect to any letter.

Indeed, let a be a letter and let C be the set of states of the form i • a j . For any state q, there exists a path i u -→ q v -→ i. We may suppose that i does not occur elsewhere on this path. Thus uv ∈ X. Since X is a finite maximal code, there is an integer j such that ua j ∈ X. Then q • a j = i belongs to C. This shows that A is one-cluster with respect to a.

A maximal prefix code X is synchronized if there is a word x ∈ X * such that for any word w ∈ A * , one has wx ∈ X * . Such a word x is called a synchronizing word for X.

Let X be a synchronized prefix code. Let A be an irreducible deterministic automaton with an initial state i such that X A = X. The automaton A is synchronized. Indeed, let x be a synchronizing word for X. Let q be a state of A. Since A is irreducible, there is a path i u -→ q for some u ∈ A * . Since x is synchronizing for X, we have ux ∈ X * , and thus q • x = i. This shows that x is a synchronizing word for A.

Conversely, let A be an irreducible complete deterministic automaton. If A is a synchronized automaton, the prefix code X A is synchronized. Indeed, let x be a synchronizing word for A. We may assume that q • x = i for any state q. Then x is a synchronizing word for X. Proposition 5. Let X be a maximal synchronized prefix code with n codewords on an alphabet of size k. The decoder of X has a synchronizing word of length at most O(( n k ) 2 ).

Proof. The automaton A X is one-cluster. The number N of its states is the number of prefixes of the words of X. Thus N = (n -1)/(k -1) since a complete k-ary tree with n leaves has (n -1)/(k -1) internal nodes. By Proposition 2, there is a synchronizing word of length at most 1 + 2(N -1)(N -2), whence O(( n k ) 2 ). When the lengths of the codewords in X are not relatively prime, the automaton A X is never synchronized (see Example of Figure 6). When the lengths of the codewords in X are relatively prime, the code X is not necessarily synchronized. However, there is always another Huffman code X ′ corresponding to the same length distribution which is synchronized by a result of Schützenberger [START_REF] Schützenberger | On synchronizing prefix codes[END_REF]. One can even choose X ′ such that the underlying graph of A X and A X ′ are the same. This is a particular case of the road coloring theorem of due to Trahtman [START_REF] Trahtman | The road coloring problem[END_REF] (see also [START_REF] Béal | A quadratic algorithm for road coloring[END_REF]). The particular case corresponding to finite prefix codes was proved before in [START_REF] Perrin | Synchronizing words and automata and the road coloring problem[END_REF].

Our result guarantees that the Huffman decoder has a synchronizing word of length at most quadratic in the number of nodes of the Huffman tree. Fig. 3. A non synchronized Huffman code X on the left and its decoder on the right. The automaton on the right is not synchronized. Indeed, for any word w, the set of states reachable by w is either {1, 3}, {2, 4}, {1, 5}, or {1, 6}.

Notes a

The present work recently inspired follow-up results. Recently, Steinberg showed how to recover our result and the bounds from [START_REF] Rystsov | Quasioptimal bound for the length of reset words for regular automata[END_REF], [START_REF]Strongly transitive automata and the Cerný conjecture[END_REF], [START_REF]The synchronization problem for locally strongly transitive automata[END_REF] using probability arguments. He also obtained the Černý bound for one-cluster automata with prime length cycle in [START_REF] Steinberg | The Černý conjecture for one-cluster automata with prime length cycle[END_REF].

  linear representation of dimension d of a series S is a triple (λ, µ, γ) where λ ∈ K 1×d , µ is a morphism from A * to K d×d , and λ ∈ K d×1 , such that S, u = λµ(u)γ.

Example 6 .Fig. 2 .

 62 Fig.2. A synchronized Huffman code X on the left and its decoder A X on the right.