Thomas Colcombet

Laure Daviaud

Approximate comparison of distance automata

Distance automata are automata weighted over the semiring (N ∪ {∞}, min, +) (the tropical semiring). Such automata compute functions from words to N∪{∞} such as the number of occurrences of a given letter. It is known that testing f g is an undecidable problem for f, g computed by distance automata. The main contribution of this paper is to show that an approximation of this problem becomes decidable.

We present an algorithm which, given ε > 0 and two functions f, g computed by distance automata, answers yes if f

(1 -ε)g, no if f g, and may answer yes or no in all other cases. This result highly renes previously known decidability results of the same type.

The core argument behind this quasi-decision procedure is an algorithm which is able to provide an approximated nite presentation to the closure under product of set of matrices over the tropical semiring.

We also provide another theorem, of ane domination, which shows that previously known decision procedures for cost-automata have an improved precision when used over distance automata.

Introduction

One way to see language theory, and in particular the theory of regular languages, is as a toolbox of constructions and decision procedures allowing high level handling of languages. These high level operations can then be used as black-boxes in various decision procedures, such as in verication.

Since the early times of automata theory, the need for the eective handling of functions rather than sets (as languages) was already apparent. Schützenberger proposed already in the sixties models of nite state machines used for computing functions. These are now known as weighted automata [START_REF] Schützenberger | On the denition of a family of automata[END_REF] and are the subject of much attention from the research community. In general, weighted automata are non-deterministic automata, weighted over some semiring (S, ⊕, ⊗). The value computed by such an automaton over a given word is then the sum (for ⊕) over every run over this word of the product (for ⊗) of the weights along the run.

Several instances of this model are very relevant for modelling the behaviour of systems, and henceforth attract much attention. This is in particular the case of probabilistic automata (over the semiring (R + , +, ×) with some additional constraints enforcing weights to remain in [0, 1]), and distance automata which

The research leading to these results has received funding from the European Union's Seventh Framework Programme (FP7/2007-2013) under grant agreement n o 259454.

are automata weighted over the semiring (N ∪ {∞}, min, +). In such an automaton, each transition is labelled with a non-negative integer (usually 0 or 1), and the weight of a word is the minimum over all possible paths of the sum of the weights. These automata naturally capture some optimisation problems since computing the value amounts to nd the path of minimal weight.

The subject of this paper is to develop algorithmic tools for distance automata, and more precisely to develop the question of comparing distance automata. We know from the beginning that exact comparison is beyond reach.

Theorem 1 (Krob [6]). The problem to determine, given two functions f, g computed by distance automata, whether f = g or not is undecidable. The problem whether f g or not is also undecidable, even if g is deterministic.

Despite this, some positive results exist but for a comparison relation less precise than inequality, namely the domination. Given two functions A * → N ∪ {∞}, f is dominated by g (and we note f g) if there is a function α : N → N, extended with α(∞) = ∞, such that f α • g .

Moreover, if α is a polynomial, we say that f is polynomially dominated by g.

The following theorem shows the good properties of the domination relation.

Theorem 2 ( [START_REF] Colcombet | The theory of stabilisation monoids and regular cost functions[END_REF] extending results and techniques from [START_REF] Hashiguchi | Limitedness theorem on nite automata with distance functions[END_REF][START_REF] Leung | On the topological structure of a nitely generated semigroup of matrices[END_REF][START_REF] Simon | On semigroups of matrices over the tropical semiring[END_REF][START_REF] Daniel | Distance desert automata and the star height problem[END_REF][START_REF] Boja | Bounds in ω-regularity[END_REF]).

Given two functions computed by distance automata, domination is decidable. Furthermore, if a function dominates another, then it polynomially dominates it 1 .

The motivation of this work is to improve Theorem 2, and answer the following question:

Is it possible to decide approximations of the inequality of functions computed by distance automata that are ner than domination ?

We answer positively this question in two ways. We rst show:

Theorem 3 (ane domination). Given two functions f and g computed by distance automata, if f is dominated by g then f is anely dominated by g, i.e., f α • g for some polynomial α of degree 1.

A consequence of this theorem is that the decision procedure provided by Theorem 2 in fact decides the ane domination, which is ner than the polynomial domination 2 .

Our second, and main contribution is an even more accurate decision-like procedure. One says that an algorithm, given two functions f and g and some real ε > 0, ε-approximates the inequality if:

1 Technically, this is not stated in [START_REF] Colcombet | The theory of stabilisation monoids and regular cost functions[END_REF] , but can be derived directly from the proofs which explicitly compute the function α using operations preserving polynomials.

2 Theorem 2 holds for more general classes of automata, cost automata, for which ane domination does not hold. Ane domination is specic to distance automata.

if f (1 -ε)g, the output is yes, if f g, the output is no, otherwise the output can be either yes or no.

Hence, if such an algorithm answers yes, one has a guaranty that f g.

Conversely if f is ε-inferior to g (meaning f
(1 -ε)g), one is sure that the algorithm answers yes. Our second and main result reads as follows:

Theorem 4 (approximate comparison). There is an EXPSPACE algorithm which ε-approximates the inequality of functions computed by distance automata.

This result is in fact a consequence of a theorem called the core theorem below stating that it is possible, given a set of matrices X in the tropical semiring, to approximate (in a suitable way) the set

1 k (M 1 ⊗ • • • ⊗ M k ) : M 1 , . . . , M k ∈ X ,
where ⊗ denotes the product of matrices. More precisely, the core theorem states that it is possible to approximate the upper envelope of the set of pairs

{(M 1 ⊗ • • • ⊗ M k , k) : M 1 , . . . , M k ∈ X} for a suitable notion of approximation.
This core theorem, Theorem 5, will be described precisely in the rst section of this paper.

In Section 2 we present some classical denitions and formally state our core theorem. Section 3 is devoted to the proof of the core theorem. Section 4 applies the core theorem for answering our original motivation, and shows the decidability of the approximate comparison between distance automata. We prove on the way our result of ane domination, Theorem 3. Section 5 concludes the paper.

2 Description of the core theorem

In this rst section, we introduce the basic denitions, and dene sucient material for stating our core theorem 5. Its proof is the subject of Section 3 and its application to the comparison of distance automata is the subject of Section 4.

We rst introduce some classical algebraic denitions in Section 2.1, and nally state our core theorem in Section 2.2.

Classical denitions

A semigroup (S, •) is a set S equipped with an associative binary operation •. If the product has furthermore a neutral element, it is called a monoid. The monoid is said commutative when • is commutative. An idempotent in a monoid is an element e such that e•e = e. Given a subset A of a semigroup, A denotes the closure of A under product, i.e., the least sub-semigroup that contains A.

Given two subsets X, Y of a semigroup, X • Y denotes the set {a • b : a ∈ X, b ∈ Y }.
A semiring is a set S equipped with two binary operations ⊕ and ⊗ such that (S, ⊕) is a commutative monoid of neutral element 0, (S, ⊗) is a monoid of neutral element 1, 0 is absorbing for ⊗ (i.e., x ⊗ 0 = 0 ⊗ x = 0) and ⊗ distributes over ⊕. We will consider three semirings: (R + ∪ {∞}, min, +), denoted R + , its restriction to N ∪ {∞}, denoted N, and its restriction to {0, ∞} denoted B. The third, nite semiring is called the Boolean semiring, since if we identify 0 with true and ∞ with false, then ⊕ is the disjunction and ⊗ the conjunction. Remark that in the three cases, the 0 is ∞, and the 1 is 0.

Let S be one of the above semirings. The set of matrices with m rows and n columns over S is denoted M m,n (S). For M ∈ M m,n (S), we denote by M the matrix over B in which all entries of M dierent from ∞ are changed into 0. We dene the multiplication A ⊗ B of two matrices A, B (provided the number n of columns of A equals the number of rows of B) as usual by:

(A ⊗ B) i,j = 0<k n (A i,k ⊗ B k,j ) = min 0<k n (A i,k + B k,j ) .
For a positive integer k, we also use the notation

M k = M ⊗ • • • ⊗ M k times .
For λ ∈ S, we denote by λA the matrix such that (λA) i,j = λA i,j , with the convention λ∞ = ∞ (the standard product is used here, not the one of the semiring). Finally, we denote by B +λ the matrix such that (B +λ) i,j = B i,j +λ.

Weighted matrices and the core theorem

In this section we state our core approximation result, Theorem 5. This theorem states that given a set of weighted matrices, it is possible to compute a nite presentation of its closure under product up to some approximation. Hence we have to introduce weighted matrices, the approximation, and what are nite presentations before disclosing the statement. This requires some specic denitions that we present beforehand. In the following, a positive integer n is xed, and all matrices implicitly belong to M n,n (R + ).

As already mentioned in the introduction, our goal is to approximate a set of pairs (M, ) where M is a matrix and is a positive integer. We call such pairs weighted matrices. A weighted matrix is an ordered pair (M, ) where M ∈ M n,n (R + ) and ∈ N is non-null. The positive integer is called the weight of the weighted matrix. The set of weighted matrices is denoted by W n,n .

Weighted matrices have a semigroup structure (W n,n , ⊗), where (M, )⊗(M , ) stands for (M ⊗ M , + ). Given A, B subsets of W n,n , one denotes by A ⊗ B the set {M ⊗ N : M ∈ A, N ∈ B}, and by A the closure under ⊗ of A. With this terminology, our goal is, given a nite set of weighted matrices X, to approximate X .

We describe now the notion of approximation that we use. Given some ε > 0 and two weighted matrices (M, ) and (M , ), one writes

(M, ) ε (M , ) if , M = M and M M + ε .
Remark that in particular, this implies 1 M 1 M + ε, which is the intention behind this denition. The denition of ε is more constraining: this is manda- tory for having better properties with respect to the product of matrices, such as in Lemma 1 below. This denition extends to sets of weighted matrices as follows. Given two such sets X, X , X ε X if for all (M, ) ∈ X, there exists (M , ) ∈ X such that (M, ) ε (M , ). One writes X ≈ ε X if X ε X and X ε X (and says X is ε-equivalent to X ).

The following lemma establishes some simple properties of the ε relations (as a consequence, the same properties hold for ≈ ε ).

Lemma 1. Given X, X , Y, Y , Z ⊆ W n,n and ε, η > 0, if X ε Y and Y η Z then X ε+η Z, if X ε X and Y ε Y then X ⊗ Y ε X ⊗ Y , if X ε X then X ε X . Proof. First item. If (M, ) ε (M , ) η (M , ), then , M = M = M and M M + ε M + η + ε M + (ε + η)
. This easily extends to sets of weighted matrices.

Second item. Assume (M, ) ε (M , ) and (N, t) ε (N , t ). Then, +

t+t , M ⊗ N = M ⊗ N and M ⊗N (M +ε )⊗(N +εt) M ⊗N +ε( +t).
This naturally extends to sets of weighted matrices.

Third item. By induction, applying the second item.

The last ingredient required is to describe how to represent (innite) sets of weighted matrices. Call a set of weighted matrices W ⊆ W n,n nitely presented if it is a nite union of singleton sets, and of sets of the form {(kM, k) : k } where M ∈ M n,n (R + ) and is a positive integer. Our algorithm manipulates nitely presented sets of weighted matrices.

The core technical contribution of this paper can now be stated, as follows.

Theorem 5 (core theorem). Given X ⊆ W n,n nitely presented and ε > 0, one can compute eectively Y ⊆ W n,n nitely presented such that:

Y ≈ ε X .
A sketch of the proof of this result will be the subject of Section 3. The application of this theorem to the comparison of distance automata is presented in Section 4. The two sections are independent.

Proof of the core theorem

In this section we describe the key arguments involved in the proof of Theorem 5. It is the combination of several arguments. The rst one is the use of the factorisation forest theorem of Simon.

The main induction: the forest factorization theorem of Simon

The forest factorization theorem of Simon [START_REF] Simon | Piecewise testable events[END_REF] is a powerful combinatorial tool for understanding the structure of nite semigroups. In this short abstract, we will not describe the original statement of this theorem, in terms of trees of factorisations, but rather a direct consequence of it which is central in our proof.

Proposition 1 (equivalent to the forest factorization theorem [START_REF] Simon | Piecewise testable events[END_REF] 3 ).

Given a semigroup morphism φ from (S, ⊗) (possibly innite) to a nite semigroup (T, •), and some X ⊆ S, set X 0 = X and for all k 0,

X k+1 = X k ∪ X k ⊗ X k ∪ e•e=e∈T X k ∩ φ -1 (e) , then X N = X for N = 3|T | -1.
This proposition teaches us that, for computing the closure under product in the semigroup S, it is sucient to know how to compute (a) the union of sets, (b) the product of sets, and (c) the restriction of a set to the inverse image of an idempotent by φ, and (d) the closure under product of sets of elements that all have the same idempotent image under φ. Of course, this proposition is interesting when the semigroup T is cleverly chosen.

In our case, we are going to use the above proposition with (S, ⊗) = W n,n , (T, •) = M n,n (B), and φ the morphism which maps (M, ) to M . Our algorithm will compute, given a nitely presented set of weighted matrices X, an approximation of X following the same inductive construction as in the forest factorisation theorem. This is justied by the two following lemmas, that we prove below. Lemma 2. For all ε > 0 and all nitely presented X, Y ⊆ W n,n there exists eectively product(ε, X, Y ) ⊆ W n,n nitely presented such that

product(ε, X, Y ) ≈ ε X ⊗ Y . Let X be a set of weighted matrices, we denote X = { M | ∃ > 0 s.t (M, ) ∈ X}.
Lemma 3. For all ε > 0 and all nitely presented X ⊆ W n,n such that X = {e} for an idempotent e, there exists eectively idempotent(ε,

X) ⊆ W n,n nitely presented such that idempotent(ε, X) ≈ ε X .
Assuming that Lemmas 2 and 3 hold, it is easy to provide an algorithm which, given X ⊆ W n,n nitely presented, computes X ⊆ W n,n nitely presented such that X ≈ ε X . The principle of the algorithm is to implement Proposition 1, using nitely presented sets that approximate the X k 's.

3 Modern proofs of this theorem can be found in [START_REF] Kueitner | A proof of the factorization forest theorem[END_REF][START_REF] Colcombet | Green's relations and their use in automata theory[END_REF], in particular with the exact bound of N = 3|T | -1 (Simon's original proof only provides N = 9|T |).

Set Y 0 = X and N = 3(2 n 2 ) -1. For all 0 k N , set ε(k) = ε 2 N -k and Y k+1 = Y k ∪ product(ε(k), Y k , Y k ) ∪ e⊗e=e∈T idempotent(ε(k), Y k ∩ φ -1 (e)) .
output Y N It is easy to prove that this construction is correct. Indeed, one proves by in-

duction that Y k ≈ ε(k) X k for all k = 0, . . . , N where X k is dened as in Propo- sition 1 (with S = W n,n , T = M n,n (B) and φ(M, ) = M ). For k = 0, one has X k = X = Y k . Let k 0, suppose that Y k ≈ ε(k) X k , then by Lemma 2, Lemma 1 and the induction hypothesis, product(ε(k), Y k , Y k ) ≈ ε(k) Y k ⊗ Y k ≈ ε(k) X k ⊗ X k . Finally, by Lemma 1, product(ε(k), Y k , Y k ) ≈ 2ε(k) X k ⊗X k . Similarly, by Lemma 3, for all idempotent e, idempotent(ε(k), Y k ∩ φ -1 (e)) ≈ 2ε(k) X k ∩ φ -1 (e) . Thus Y k+1 ≈ ε(k+1) X k+1 .
Hence, what remains to be done is to establish Lemmas 2 and 3.

Approximate products of sets

The proof of Lemma 2 shows explicit examples of the approximation arguments that are later used in a more advanced way.

Proof (Proof of Lemma 2). Since the nitely presented sets of weighted matrices are closed under union, it is sucient to prove Lemma 2 for the atomic blocks of the nite presentation. Namely, it is sucient to consider the case

X = {(M, x)} or X = {( M, ) | x} together with Y = {(N, y)} or Y = {( N, ) | y}.
This results in four possibilities, among which only three remain up to symetry:

(a) X = {(M, x)} and Y = {(N, y)}, (b) X = {(M, x)} and Y = {( N, ) | y}, and nally (c) X = {( M, ) | x} and Y = {( N, ) | y}.
For space reason, let us just explain the most interesting case, case (c). Let a be the maximum absolute value of a non-innite entry of M or N . Choose some z such that 2ax εz and 2ay εz, and let Z be the set Z 1 ∪ Z 2 dened by:

Z 1 = {(x M ⊗ y N, x + y ) | x + y < z} , and Z 2 = {( (λM ⊗ (1 -λ)N ), ) | z, λ ∈ [0, 1]} .
The set Z 1 is nite, and merely lists all weighted matrices of weight less than z in X ⊗ Y . The set Z 2 (which is not nitely presented) takes all barycentres of M and N , and produces corresponding weighted matrices for all possible weights greater or equal to z. We need to prove two things. First that Z ≈ ε 2 X ⊗ Y , and second that one can further approximate Z 2 by a nitely presented

Z 3 ≈ ε 2 Z 2 . By Lemma 1 we can then conclude that X ⊗ Y ≈ ε Z 1 ∪ Z 3 , and that Z 1 ∪ Z 3 is nitely presented and computable from X and Y . Let us prove that Z ≈ ε 2 X ⊗Y . Remark rst that X ⊗Y ⊆ Z. For the converse direction, consider (W, ) ∈ Z. Clearly, if < z, then (W, ) ∈ Z 1 ⊆ X ⊗ Y . Otherwise, W = (λ M ) ⊗ ((1 -λ) N )). It is sucient for us to nd x
x and y y such that x +y = , and λ -x ε 2a : indeed, assuming the existence of such x , y , the matrix W = (x M ⊗ y N, ) is such that (W, ) ≈ ε 2 (W , ), and furthermore (W , ) ∈ X ⊗ Y . For proving the existence of such x , y , consider the evolution of the value x when x ranges from x to -y. Since z, x ε 2a , and similarly -y

1 -ε 2a . Furthermore when x increases of 1, the quantity

x increases of at most 1 z ε 2a . As a consequence, x gets to be ε 2a -close of any λ ∈ [0, 1] when x ranges from x to -y. Consider x witnessing this fact and set y = -x . The pair x , y satises the requirement.

One now needs dening a set Z 3 ≈ ε 2 Z 2 which is nitely presented. The set Z 3 is dened as the set Z 2 , but for the fact that λ is discretized by steps of ε 4a .

This can be written as:

Z 3 = λ∈([0,1]∩ ε 4a N) {( (λM ⊗ (1 -λ)N ), ) | z} .
Clearly, this set is nitely presented. It is also simple to prove that

Z 3 ≈ ε 2 Z 2 .
Details of the complete proof are given in Section A.

Approximate idempotent products of sets

We enter here the most technical part of the proof. We just sketch here the essential ideas. Let us x ourselves an idempotent E ∈ M n,n (B), some ε > 0, and some nitely presented set of weighted matrices X such that X = {E}. Our goal is to construct a nitely presented X such that X ≈ ε X . In this section, all matrices and weighted matrices M are supposed to be such that M = E.

The proof is done in several steps. We rst dene two restricted notions of closure. Let p be some positive integer and η > 0. Dene X p,η to be the set of weighted matrices

(M, ) = (M 1 , 1 ) ⊗ • • • ⊗ (M k , k )
where each (M i , i ) belongs to X, and there exists i

1 < • • • < i s with s p such that s j=1 ij (1 -η) (where = k j=1 j ).
In other words, k can be very large, but there are only few weighted matrices (less than p) that count for most of the weight (ratio 1 -η). If furthermore 1 η and k η , the product is said uniform. Set X u p,η to be the set of weighted matrices obtained by such uniform products.

The following lemma shows that X p,η and X u p,η can be eectively approx- imated (for suciently small choices of η).

Lemma 4. For all γ > 0, there exists η > 0 such that for all nitely presented X with X = {E} and all p, there exist eectively Y and Z nitely presented such that:

Y ≈ γ X p,η and Z ≈ γ X u p,η .
The idea behind this proof is that the set X p,η is essentially like a product of up to p weighted matrices (something we know how to do as shown in Lemma 2), but modied in order to possibly interleave in the product matrices of small weights. One chooses η suciently small such that all these matrices of small weight can be approximated by matrices of null weight.

Our second intermediate lemma shows that any product of weighted matrices in X can be decomposed into products as the above restricted closures. Lemma 5. For all X such that X = {E} for some idempotent E, for all η > 0, there is an integer p, such that:

X = X p,η ⊗ X u p,η ⊗ X p,η .
Here, the lemma comes from a careful analysis of the proportions between weights in any product

(M 1 , 1 ) ⊗ • • • ⊗ (M k , k ).
At this point one should understand why computing X u p,η is simpler than computing X as in the general case. The reason is that the weighted matrices in X u p,η have particularly good properties. Call a matrix M (such that M = E)

uniform if M = E ⊗ M ⊗ E. A weighted matrix (M, ) is uniform if M is uniform.
The following lemma shows that every matrix in X u p,η is almost uniform. Lemma 6 states it and renes Lemma 4.

Lemma 6. For all γ > 0, there exists η > 0 such that for all nitely presented X with X = {E} and all p, there exist eectively Z nitely presented such that:

Z ≈ γ X u p,η ,
and all weighted matrices in Z are uniform.

Intuitively, this comes from the fact that weighted matrices in X u p,η are dened as products that starts and ends with matrices of small weight. If these weights are suciently small, these matrices count as if of null weight. Thus, these extremity matrices act as multiplying on the left and on the right with E.

This yields matrices that are very close to uniform ones.

Finally, one shows that it is possible, given a nitely presented set Y of uniform weight matrices, to compute its closure.

Lemma 7. For all η and all nitely presented set Y of uniform weight matrices (with Y = E), there exists eectively Z nitely presented such that:

Z ≈ η Y .
This results comes from the fact that one understands precisely the structure of uniform matrices (for instance, if we see such a matrix as a weighted graph, then the weight of transitions are constant in strongly connected component).

Using this knowledge, it is possible to show that the worst situation occurs for very simple patterns of repetition of the matrices in Y . Since the relation ≈ η just refers to the upper envelope, this worst situation is sucient for us to conclude.

The combination of all the above lemmas yields quite simply a proof of Lemma 3. Details of the proof are given in Section B.

Comparing distance automata

In this section, we consider the problem of comparing the functions computed by distance automata. In particular, we establish Theorem 3, and we reduce Theorem 4 to our core theorem, Theorem 5.

We start by describing distance automata, and their relationship with matrices over the tropical semiring (Section 4.1).

Distance automata

An alphabet is a nite set. The set of words over an alphabet A is denoted A * . The empty word is λ. A distance automaton is a tuple (A, Q, I, F, T ), where Q is a nite set of states (that we can assume to be {1, . . . , n}) where I (resp.

T ) is a row-vector (resp. column-vector) indexed by Q, and F is a morphism from words to M n,n (N). The function f computed by a distance automaton (A, Q, I, F, T ) over an input word u is:

f : A * → N u → I ⊗ F (u) ⊗ T .
We assume from now on that the initial and nal vectors I, T of distance automata only range over {0, ∞}. The theorems are equally true without this assumption, but this simplies slightly the proof. In practice the theorems without this restriction can be obtained by simple reductions to this case.

We have dened so far distance automata in terms of matrices. One can see this object in a more automaton form as follows. There is a transition labelled (a, x) from state p to state q if x < ∞ and x = F (a) p,q . A state p is initial if I 1,p = 0. It is nal if T i,1 = 0. An example of distance automaton is as follows: A run of an automaton over a word a 1 . . . a k is a sequence p 0 , . . . , p k of states. The weight of a run is the sum of the weights of its transitions, i.e., F (a 1 ) p0,p1 +

• • • + F (a k ) p k-1 ,p k .
Remark that if there is some non-existing transition in this sequence, say from p i-1 to p i , this means that F (a i ) pi-1,pi = ∞, and as a consequence the run has an innite weight. A run is accepting if p 0 is initial and p k is nal. One denes the function accepted by the automaton as:

f : A * → N u → inf{weight(ρ) : ρ accepting run over u} .
This denition is equivalent to the matrix version presented above.

For instance, the function computed by the above automaton associates to each word u = a n0 ba n1 . . . ba n k the value min(n 0 , . . . , n k ).

Superior limits

In this section, we present Theorem 6. This result, that is a renement of known proofs concerning distance automata, will prove useful for further reductions.

In order to dene the superior limit of a set of matrices, a topology is required. The matrices over N are equipped with the following topology. When two matrices are distinct, their distance is 1/n where n is maximal positive integer such that the entries that carry values at most n are the same in both matrices.

If no such integer exists, the distance is 1.

Given X ⊆ M n,n (N), a matrix N belongs to the superior limit of X if:

N is the limit of some sequence of matrices from X, there exists no M ∈ X such that M > N .

Let us call lim sup(X) the set of matrices in the superior limit of S.

Theorem 6 (consequence of [START_REF] Hashiguchi | Limitedness theorem on nite automata with distance functions[END_REF][START_REF] Leung | On the topological structure of a nitely generated semigroup of matrices[END_REF]). Given a set X ⊆ M n,n (N), lim sup(X) is nite. Furthermore, there is a PSPACE algorithm which, given a morphism F from A * to M n,n (N), and a language L ⊆ A * enumerates lim sup(F (L)).

The rst part of the statement is a consequence of Higman's lemma. The second part is an adaptation of Leung's proof of decidability of limitedness for distance automata [START_REF] Leung | On the topological structure of a nitely generated semigroup of matrices[END_REF] (it subsumes this result). We are not aware of any similar statement in the literature, though it can be deduced from previous works.

A rst reduction: the theorem of ane domination

Our goal in this section is to establish the theorem of ane domination (Theorem 3). This will be the opportunity to introduce some notations used in the subsequent section.

Let us x ourselves two distance automata over the same alphabet A. The rst one, A f = (A, Q f , F, I f , T f ) calculates a function f . The second one, A g = (A, Q g , G, I g , T g ) calculates a function g.

Dene R p,0,q ⊆ A * to be the set of words over which there is a run of g of weight 0 from state p to state q. Let be a non-null weight occurring in some transition of g, and p, q be states in Q g . Dene R p, ,q ⊆ A * to contain the words over which there is a run of g from state p to state q which uses one transition of weight , and otherwise only transitions of weight 0. We will reuse this languages in the next section.

Proof (Proof of theorem 3). Dene K to be the largest number that occur in one of lim sup(F (R p, ,q )) for some states p, q and weight of a transition (such a number exists since by Theorem 6 it is the maximum of nitely many numbers).

Given a matrix M , call an m-expansion of M a matrix M M such that for all i, j such that M i,j > K, M i,j m. We rst show a claim concerning expansions.

Claim. For all M ∈ F (R p, ,q ) and all m there exists an m-expansion M ∈ F (R p, ,q ) for M . Indeed, by denition of the superior limit, there is some L ∈ lim sup(F (R p, ,q )) such that L M . Furthermore, by choice of K, whenever M i,j > K, L i,j = ∞. Finally, still by denition of the superior limit, L is the limit of a sequence of matrices in F (R p, ,q ). Hence, for all m, there exists a matrix M in this sequence which is suciently close to L that it is an m-expansion of M . This proves the claim.

Let us turn now to the core of the proof. Our goal is to prove that if f is dominated by g, (i.e., there exists α : N → N extended with α(∞) = ∞ such that f α • g), then f K(1 + g). The proof is by contraposition. Thus, assume f K(1 + g). This means f (u) > Kg(u) + K for some word u. We have to prove that f is not dominated by g.

The rst case is g(u) = 0. This means that u ∈ R p,0,q with p initial and q nal. Using the above claim, one can chose for all m a word v m ∈ R p,0,q such that F (v m ) is an m-expansion of F (u). Since f (u) > K, this means that for all initial state r and all nal state s of A f , F (u) r,s > K. This means that for all such r, s, F (v m ) r,s m. It follows that f (v m ) m. Hence over the sequence (v m ) m , g is bounded and f tends to innity. This forbids the existence of a function α such that f α • g, f is not dominated by g.

Assuming g(u) = 0, the argument is similar. Remark rst that g(u) is nite since f (u) > Kg(u) + K. This means one can nd p 0 , . . . , p k with p 0 initial, p k nal, and such that:

u = u 1 . . . u k , u 1 ∈ R p0, 1 ,p1 , . . . , u k ∈ R p k-1 , k ,p k ,
where 1 , . . . , k are all non-null and of sum g(u). By the above claim, for all i = 1 . . . k, and all m, one can select

v m i in R pi-1, i,pi such that F (v m i ) is an m-expansion of F (u i ). Consider now the word v m = v m 1 . . . v m k . Clearly g(v m ) = g(u)
. For the sake of contradiction, assume now that F (v m ) < m for some m. This means that there exists q 0 , . . . , q k such that q 0 is initial, q k is nal, and

F (v m i ) qi-1,qi < m for all i = 1 . . . k. Since F (v m i ) is an m -expansion of F (u i ), this implies F (u i ) qi-1,qi K. It follows that F (u) Kk Kg(u). A contradiction. Hence f (v m ) m. Thus, g is bounded over (v m ) m while f is not.
As a consequence, f is not dominated by g.

The reduction construction

We reuse denitions and notations of automata A f and A g given in the preceding section. In particular, we use the sets R p, ,q again.

Our goal is to construct a nite set of weighted matrices X that captures the relationship between f and g. The key ideas behind this reduction are the following. Each matrix (M, ) in X corresponds to a set of runs of g, that start in a given state p and end in a given state q, and use exactly one transition of non-null weight, of weight . The corresponding matrix M is in charge of (a) simulating the behaviour of F over some word corresponding to such a run (there may be innitely many such runs, but only the nitely many matrices of the superior limit need be considered), and (b) keeping information concerning the rst and last state of the run of A g for being able to check that pieces of run of g are correctly concatenated.

One also needs to dene the part of the matrix in charge of controlling the validity of the run of A g . The construction behind Lemma ?? below is the one of a deterministic automaton, that reads words over the alphabet Q 2 g , and accepts a word (p 1 , q 1 ) . . . (p k , q k ) if, either p 1 is not initial, or q k is not nal, or if q i-1 = p i for some i. One can verify that this language is accepted by a deterministic and complete automaton of states Q g {i, ⊥}. The unique initial state is i, and, when reading the word (p 1 , q 1 ) . . . (p k , q k ), the automaton reaches state ⊥ if p 1 is not initial or q i-1 = p i for some i, otherwise it reaches state q k . The nal states are the one not in T g plus ⊥ plus possibly i if there are no states that are both initial and nal in g. Translated in matrix form, this yield Lemma 8. Lemma 8. There are (n + 2, n + 2)-matrices (C p,q ) p,q∈G over B and vectors I g and T g such that for all p 1 , q 1 , . . . , p k , q k ∈ Q g ,

I C ⊗ C p1,q1 ⊗ • • • ⊗ C p k ,q k ⊗ T C = ∞ if p 1 ∈ I g , q 1 = p 2 , . . . , q k-1 = p k and q k ∈ T g , 0 otherwise.
We can now construct the set X as follows:

X = M ∞ ∞ C p,q , : M ∈ lim sup(F (R p, ,q ))
and the vectors

I = (I f I C ) and T = T f T c .
The following lemma shows the validity of the construction, and more particularly how it relates the comparison of distance automata to the computation of the closure of a set of weighted matrices.

Lemma 9. For all β > 0, f βg if and only if for all (W, ) ∈ X , I ⊗W ⊗T β .

Proof. Assume rst f βg, which means f (u) > βg(u) for some u. Then clearly, g(u) is nite and hence, there is an accepting run ρ of g over u. This means that one can nd p 0 , . . . , p k with p 0 initial, p k nal, and such that:

u ∈ R p0, 1,p1 R p1, 2,p2 . . . R p k-1 , k ,p k ,
where 1 , . . . , k are all non-null and of sum = g(u). For all i = 1 . . . k, set M i to be some matrix in lim sup(F (R p i-1, i ,p i )) such that F (u i ) M i . Let also C i be C pi-1,pi . Clearly, the weighted matrix

(W i , i ) with W i = M i ∞ ∞ C i belongs to X. Hence (W, ) belongs to X , where W = W 1 ⊗ • • • ⊗ W k . We then have I ⊗ W ⊗ T = min(x f , x C ) with x f = I f ⊗ M 1 ⊗ • • • ⊗ M k ⊗ T f and x C = I C ⊗ C 1 ⊗ • • • ⊗ C k ⊗ T C . By choice of the M i 's, x f I f ⊗ F (u) ⊗ T f = f (u). Furthermore, by Lemma 8, x C = ∞. It follows that I ⊗ W ⊗ T f (u) > βg(u) = β .
Assume now that f βg. Consider some (W, ) ∈ X , it is obtained as (W, ) = (W 1 , 1 ) ⊗ • • • ⊗ (W k , k ) with (W i , i ) ∈ X for all i. By denition of X, each of the W i 's can be written, for some p i , q i ∈ Q g , as

W i = M i ∞ ∞ C pi,qi with M i ∈ lim sup F (R pi, i,qi ).
Once more, one has I ⊗ W ⊗ T = min(x f , x C ) with

x f = I f ⊗ M 1 ⊗ • • • ⊗ M k ⊗ T f and x C = I C ⊗ C 1 ⊗ • • • ⊗ C k ⊗ T C .
Remark rst that if x C = 0, clearly, I ⊗ W ⊗ T = 0 β . Hence, let us assume that x C = ∞. This means by Lemma 8 that either p 1 is initial, q k is nal, and p i = q i-1 for all i = 2 . . . k. One needs to prove x f β . Assume for the sake of contradiction that x f > β . By continuity of the product, and using the denition of the superior limit, there exist words u 1 , . . . , u k such that for all i = 1 . . . k, u i ∈ R pi, i,qi , and

I f ⊗F (u 1 )⊗• • •⊗F (u k )⊗T f > β .
Furthermore, by denition of the sets R pi, i,qi , the fact that p 1 is initial, that q k is nal, and that q i-1 = p i for all i = 2 . . . k, it follows that g(u 1 . . . u k ) = . It follows that f (u 1 . . . u k ) > βg(u 1 . . . u k ). A contradiction.

We are now ready to establish the main theorem of the paper.

Proof (Proof of Theorem 4). Let us consider two functions f and g computed by distance automata and some ε > 0. The algorithm works as follows. It computes the set X of weighted matrices as dened in this section, as well as the corresponding vectors I, T . Using Theorem 5, it computes a nitely presented set Y of weighted matrices such that Y ≈ ε 2 X . Then it tests the existence in Y of a weighted matrix (M, ) such that I ⊗ 1 M ⊗ T > 1 -ε 2 . This is easy to do for nitely presented sets. If such a weighted matrix exists, the algorithm answers no. It answers yes otherwise. Let us show the correctness of this approach.

Assume f (1 -ε)g, and that, for the sake of contradiction, the algorithm answers no. This means that I ⊗ 1 M ⊗ T > 1 -ε 2 for some weighted matrix (M, ) ∈ Y . Furthermore, there exists (M , ) ∈ X such that (M, )

ε 2 (M , ). This implies 1 M 1 M + ε 2 . It follows that I ⊗ M ⊗ T > (1 -ε) .
This contradicts Lemma 9.

Assume f g, then by Lemma 9, there exists a matrix M ∈ X such that

I ⊗ 1 M ⊗ T > 1. Furthermore, there exists M ∈ Y such that (M, ) ε 2 (M , ). This implies 1 M 1 M + ε 2 , and hence I ⊗ 1 M ⊗ T > 1 -ε 2 .
The algorithm answers no.

Conclusion and further remarks

In this paper, we have provided an algorithm for deciding the approximate comparison of distance automata. This algorithm involves the computation of the closure under product of sets ofwhat we callweighted matrices. This result can be of independent interest.

The main open question is the complexity of the problem. It is clear that the problem is at least PSPACE hard. A correct implementation of the arguments in this paper show that EXSPACE is an upper bound. We do not know what is the exact complexity.

In Section A, we give the complete proof of Lemma 2 and in Section B the one of Lemma 3. These two lemmas are stated in Section 3 to prove Theorem 5.

Section C is devoted to give the proof of Lemma

( 1 M 1 ⊗ • • • ⊗ p M p , ) and ( 1 M 1 ⊗ 2 M 2 ⊗ • • • ⊗ p M p , )
, provided that coecients i and i were suciently close.

Lemma 10. For all ε > 0, for all a 0, for all positive integer p, there is η > 0 such that for all integers 1 , 2 , . . . , p , 1 , 2 , . . . , p , , and for all matrices M 1 , M 2 , . . . , M p whose greatest entry is a, we have:

if for all i, | ii | η then:

( 1 M 1 ⊗ 2 M 2 ⊗ • • • ⊗ p M p , ) ε ( 1 M 1 ⊗ 2 M 2 ⊗ • • • ⊗ p M p , ) .
Proof. Set η = ε/pa, we have:

1 M 1 ⊗ • • • ⊗ p M p ( 1 + η )M 1 ⊗ • • • ⊗ ( p + η )M p ( 1 M 1 + aη ) ⊗ • • • ⊗ ( p M p + aη ) 1 M 1 ⊗ • • • ⊗ p M p + (paη) .
As for Lemma 11, it deals with the products of the sets {( M i , ), x i }. It states that, provided that is large enough, we obtain all the products (barycen-

tre) ( (λ 1 M 1 ⊗ • • • ⊗ λ p M p ), ) with p i=1 λ i = 1.
Lemma 11. Let x 1 , x 2 , . . . , x p be positive integers. For all η > 0, there is a positive integer z such that, for all k z, for all 0 λ 1 , λ 2 , . . . , λ p 1 with p i=1 λ i = 1, for all i, there are integers y i x i such that p j=1 y j = k and |y i -λ i k| ηk.

Proof. Let x 1 , x 2 , . . . , x p be positive integers and η > 0. Denote by x the positive integer max {1 i p} x i . Set z a positive integer such that z 2px η and z > 2p 2 x. Let k z and 0 λ 1 , λ 2 , . . . , λ p 1 with p i=1 λ i = 1.

If λ i x k , set y i = x. Set Γ the set of such indices. If x k < λ i 2px k , then there is a i > 0 such that: λ i -η a i x k λ i (a i + 1)x k λ i + η (since x k η). Set Γ the set of such indices. If λ i > 2px
k , then there is a i > 0 such that:

λ i -η a i px k (a i + 1)px k λ i (a i + 2)px k λ i + η (since px k η 2 ).
Now, let q = k -|Γ |x -i∈Γ a i x -i∈Γ a i px, thanks to (2), observe that q |Γ |x + 2|Γ |px and since |Γ | 1 and thanks to (1), also observe that q 0.

One can write q = 2pxα + β with β 2px. If α < |Γ |, then for i ∈ Γ set y i = a i , for α indices in Γ set y i = (a i + 2)px, for one index in Γ set y i = a i px + β, and for the other ones set y i = a i px.

If α |Γ |, then we can rewrite q = 2px|Γ | + γ with γ |Γ |x. For i ∈ Γ , set y i = (a i + 2)px, and for i ∈ Γ , if γ = |Γ |x then set y i = (a i + 1)x, otherwise one can write γ = δx + µ with δ < |Γ | and µ < x. For δ indices in Γ set y i = (a i + 1)x, for one index in Γ set y i = a i x + µ, and for the other ones set y i = a i x.

One can easily check that the integers y i satisfy the conditions.

Lemma 12 (generalisation of Lemma 2). For all ε > 0, and nitely presented sets X 1 , . . . , X p ⊆ W n,n , there is a computable and nitely presented set Z such that:

Z ≈ ε X 1 ⊗ • • • ⊗ X p .
Proof. Assume Lemma 12 is true for p = 2, then by induction, using Lemma 1, it will be true for all the integers p. Let us prove Lemma 12 for p = 2. Let ε > 0 and X and Y be two sets as in the lemma. Since the nitely presented sets of weighted matrices are closed under union, it is sucient to prove Lemma 12 for the atomic blocks of the nite presentation.

  One can redene the function computed by a distance automaton as follows.

  If X = {(M, )} and Y = {(M , )}, then we can choose Z = {(M ⊗ M , + )}. If X = {(M, )} and Y = {(yN, y) | y k}, set a the greatest coecient of 1 M and N . For p = 2, consider η given by Lemma 10. Set z an integer such that z k + and z 1-ηη . Set Z = Z 1 ∪ Z 2 with Z 1 = k y<z {(M ⊗ yN, + y)} and Z 2 = {(y( M ⊗ N ), y) | y + z} .Then Z is nitely presented. We only need to prove that X ⊗ Y ≈ ε Z.• Let (M, ) ⊗ (yN, y) = (M ⊗ yN, + y) ∈ X ⊗ Y with y k. If k y < z, then (M, ) ⊗ (yN, y) ∈ Z 1 .If y z then η(y + ), thus by Lemma 10, we get:(M, ) ⊗ (yN, y) ε ( M ⊗ (y + )N, y + ) = ((y + )( M ⊗ N ), y + ) ∈ Z 2 .• Conversely, rst Z 1 ⊆ X ⊗ Y . Furthermore, for y + z we have (y( M ⊗ N ), y) = ( M ⊗ yN, y) and by Lemma 10, ( M ⊗ yN, y) ε (M ⊗ (y -)N, y) = (M, ) ⊗ ((y -)N, y -) ∈ X ⊗ Y .

For

  X = {(xM, x) | x } and Y = {(N, k)}, it is the same thing. If X = {(xM, x) | x} and Y = {(yN, y) | y k}, let a be the greatest coecient of M and N and consider η given by Lemma 10 (for p = 2). Set z the integer given by Lemma 11 for p = 2, x 1 = and x 2 = k and η. Finally, set Z = Z 1 ∪ Z 2 with:Z 1 = {(xM ⊗ yN, x + y) | x < z, k y < z} and Z 2 = λ∈([0,1]∩ηN) {(t(λM ⊗ (1 -λ)N ), t) | t z} .Z is nitely presented and X ⊗ Y ≈ ε Z. Indeed:• let (xM, x)⊗(yN, y) ∈ X ⊗Y . If x < z and y < z, (xM, x)⊗(yN, y) ∈ Z 1 . Otherwise, (xM, x) ⊗ (yN, y) = ((x + y)( x x+y M ⊗ y x+y N ), x + y) with x + y z. Then there is λ ∈ ([0, 1] ∩ ηN) such that | x x+y -λ| η and thus | y x+y -(1 -λ)| η, so by Lemma 10, (xM, x) ⊗ (yN, y) ε ((x + y)(λM ⊗ (1 -λ)N ), x + y) ∈ Z 2 . • First Z 1 ⊆ X ⊗ Y . Let (t(λM ⊗ (1 -λ)N ), t) ∈ Z 2with t z. By Lemma 11, there are x and y k such that x + y = t, |x -λt| ηt and |y -(1 -λ)t| ηt. By Lemma 10, we get: (t(λM ⊗ (1 -λ)N ), t) ε ((x + y)( x x + y M ⊗ y x + y N ), x + y) ∈ X ⊗ Y .

  Actually, in this part, we prove a generalisation of Lemma 2. We consider a product of p weighted matrices, for an integer p, (and not only a product of 2 weighted matrices). Lemma 12 exhibits a nitely presented set that approximates a product of p nitely presented sets. First, we state two lemmas used in the proof. We state them in the general case too. (Lemma 2 only needs the case where p = 2, but the proof of Lemma 3 uses Lemmas 10, 11 and 12 in a more

	8, stated in Section 4.
	A Proof of Lemma 2
	general way.)
	First, Lemma 10 says that given a bounded number of weighted matrices, it is
	possible to bound the dierence between two products in these matrices, namely
	between

  Set Γ the set of such indices and remark that |Γ | 1 (since p i=1 λ i = 1, and 2p 2 x k > 1).

	Since	p i=1 λ i = 1, then
		a i x +	(1)
		i∈Γ
		k
		|Γ |x +

i∈Γ a i px i∈Γ a i x + i∈Γ (a i + 1)px i∈Γ (a i + 1)x + i∈Γ (a i + 2)px .

B Proof of

 Lemma 3In this part, we prove Lemma 3 that exhibits a nitely presented set that approximates the closure of a nitely presented set in which all the matrices have the same idempotent projection (i.e there is an idempotent matrix E such that for all (M, ), M = E).

There are three steps in the proof. In the rst step (Lemma 17), we split a product of weighted matrices into simpler products (in a sense given in Subsection 3.3). Lemmas 13, 14, 15, 16 are required to prove it. In the second step, we show that some of these simpler products are ε-equivalent to nitely presented sets, and other ones are ε-equivalent to the closure under products of nitely presented and uniform sets. This is the aim of Lemma 18. The third step is devoted to give a nitely presented set ε-equivalent to the closure of nitely presented and uniform sets. It is the aim of Lemma 19.

Lemma 13. The function:

is increasing over [0, 1] r (in the sense that if for all i, x i y i , then f (x 1 , x 2 , . . . , x r ) f (y 1 , y 2 , . . . , y r )).

Proof. For all i, we have ∂f ∂xi (x 1 , . . . , x r ) = j =i (1 -x j ) 0. Proof. We prove by induction that for all i, b

Lemma 15. Let η > 0, there exists an integer p such that, given a positive integer r and a 1 , . . . , a r non-negative numbers, there are

for all j ∈ {1, . . . , k},

for all j ∈ {1, . . . , k + 1}, there is an integer s p and a set Γ of s indices between i j-1 + 1 and i j such that i∈Γ ai ai j-1 +1+...+ai j 1 -η.

Proof. Let η > 0, set p an positive integer such that (1 -η) p-1 η. Dene i j by induction on j. Let i 0 = 0 and then, suppose we have computed i j . We set i j+1 the smallest index greater than i j such that ai j+1 ai j +1+...+ai j+1 η if it exists, and i j+1 = i k+1 = r otherwise. If i j -i j-1 p then take Γ all the indices between i j-1 + 1 and i j . Otherwise, take Γ = {i j -p + 1, . . . , i j }. Set = ij i=ij-1+1 a i and b = ij -p i=ij-1+1 a i . We are going to prove that: i∈Γ ai 1 -η. By the denition of i j , we have for all i j -p + 1 i < i j that c i = ai b+ai j -p+1+...+ai > η. Now apply Lemma 14 to (b, a ij -p+1 , . . . , a ij -1 ), we get

Besides by Lemma 13,

And hence we get:

Lemma 16. Let η > 0, there exists an integer p such that, given a positive integer r and a 1 , . . . , a r non-negative numbers, there are

for all j ∈ {1, . . . , k},

for all j ∈ {1, . . . , k}, ai j ai j-1 +1+...+ai j η, for all j ∈ {0, . . . , k}, there is s p and a set Γ of s indices between i j + 1 and i j+1 such that a∈Γ a ai j +1+...+ai j+1 1 -η.

Proof. Let η > 0. Let 0 < γ η such that 2γ -γ 2 η. Consider the integer given by Lemma 15 for γ, and set p its square. Let r be a positive integer and a 1 , . . . , a r non-negative numbers, Lemma 15 for γ gives a sequence of indices 0 = q 0 < q 1 < q 2 < . . . < q k < q k+1 = r satisfying some conditions. For all j ∈ {1, . . . , k + 1}, set b k+2-j = a qj-1+1 + . . . + a qj . Now apply Lemma 16 for γ on b 1 , b 2 , . . . , b k+1 . It gives another sequence of indices 0 = j 0 < j 1 < j 2 < . . . < j m < j m+1 = k + 1 satisfying some conditions. For t ∈ {0, . . . , m + 1}, set i m+1-t = q k+1-jt . Then indices i t satisfy the lemma.

Lemma 17 (Lemma 5 in the abstract). Let X be a set of weighted matrices, for all η > 0, there is an integer p such that:

Proof. Let η > 0, consider the integer p given in Lemma 16. We have X p,η ⊗

Lemma 18 (Lemmas 4 and 6 in the abstract). For all γ > 0, for all a 0, there exists η > 0 such that for all nitely presented set X with X = {E} for an idempotent matrix E and such that for all (M, ) ∈ X, entries of 1 M are smaller than a, and for all p, there exist eectively Y and Z nitely presented such that:

Moreover, all weighted matrices in Z can be uniform.

Proof. Let γ > 0 and a 0,

. Then X p,η ⊆ Y . (Indeed, if P ∈ X p,η , let x + p the number of matrices in this product (if it is greater or equal to p), 1 , . . . , x the weights of the matrices that do not count, and k 1 , . . . , k p the weights of the matrices that count. Then,

.) Thus, X p,η is nite (so nitely presented) and computable.

If X is innite, let be the smallest weight of a matrix in X and set k an integer such that k

is the set of products in X p,η containing at least one matrix of weight greater or equal to k. Moreover X 2 is nite, thus, by the arguments given above, X 2 p,η is nite.

Let Y the maximal set such that:

and every products in Y contain at least a matrix in X of weight greater or equal to k. We will prove that Y ≈ γ 2 X , and there is Y nitely presented such that Y ≈ γ 2 Y . Then by Lemma 1, the conclusion will follow. Consider a product P in X . By denition, there is a sequence of weighted matrices in P such that the sum of their weights has a ratio smaller than η. Thus, set P the product P in which these weighted matrices are replaced by (E, ). Then P ∈ Y and P ηa P . Hence X γ 2 Y . Consider now a product P in Y . By denition, there exists (M, ) in X (recall is the smallest weight in X). Then set P the product P in which all the matrices (E, ) are replaced by (M, ). Then since there is a matrix in P (and also in P ) of weight greater than k, the sum of the weights of the added matrices is smaller than (p + 1) ηk by denition. Hence P ∈ X . Moreover,

For all i, dene the set

We can rewrite the denition of Y :

The sets X 1 , X, X ⊗ (E, ), (E, ) ⊗ X and (E, ) ⊗ X ⊗ (E, ) are nitely presented, and so X ∪

is also nitely presented. Then by Lemma 12, for all i, there are computable and nitely presented sets

i=0 Y i is nitely presented and by Lemma 1, Y ≈ γ 2 Y . Remark that if a product is uniform (with ratio δ) then it is 2δa-equivalent to the same product in which the rst and the last matrices are replaced by E.

The weighted matrix obtained by doing such product is uniform. By restricting all the sets constructed above, by considering only the products in which the rst and last matrices have a ratio smaller than η, the same construction gives us a set Y that is equivalent to a set Z in which all the matrices are uniform.

Remark 1. We will explain what is the structure of a set of uniform matrices. Suppose M is uniform and M = E. Then, for two states i and j, we say that i and j are connected if E i,j = E j,i = 0. First remark that this relation is transitive since E is idempotent.

The main property we have is that if i and j (resp. i and j ) are connected then M i,i = M j,j (since E ⊗ M ⊗ E = M ). Then two connected states play exactly the same role. Then if M is also a uniform matrix, (with M = E), we have

Finally, remark that for all positive integer k, kM M k .

Lemma 19 (Lemma 7 in the abstract). For all η > 0, for all nitely presented set X of uniform matrices such that X = {E} for an idempotent matrix E, there exists eectively Z nitely presented such that:

Proof. Let η > 0, we can write:

For 1 i p, set M i = 1 pi P i and for 1 i q, M p+i = Q i . Let a be the greatest coecient of the matrices M i and m = p + q.

Let γ > 0 such that γ

Set r a positive integer such that r 2n(a+1) γ . Lemma 11 gives an integer z , such that for all k z , for all 0 λ 1 , . . . , λ m 1 with m i=1 λ i = 1, for all i p, there are integers y i p i and for all i q, y p+i q i such that m j=1 y j = k and |y i -λ i k| γk.

The set Z is computable and nitely presented. First, let us show that Z η X . We have Z 1 ⊆ X . Let

Let k be an integer such that p

Then, for all i p, there are integers y i p i and for all i q, y p+i q i such that

Otherwise, there is (λ i ) i=1,...,m such that for all i = 1, . . . , m -1, λ i ∈ γN, m i=1 λ i = 1 and for all i = 1, . . . , m, |λ i -λ i | mγ.

Then we only need to prove that:

Let α and β be two states. Let ξ be one of the states such that E α,ξ = E ξ,β = 0, and (λ

sµ. (It is due to the structure of a set of uniform matrices.) Then, µ -nµr -1

Lemma 20 (Lemma 3 in the abstract). For all ε > 0, for all nitely presented set X such that X = {E} for an idempotent matrix E, there exists eectively Z nitely presented such that:

Proof. Let ε > 0, let η given by Lemma 18 applied to ε 4 .

By Lemma 17, there is p such that:

By Lemma 18, there is T and V nitely presented such that X p,η ≈ ε 4 T and X u p,η ≈ ε 4 V . Moreover, all the weighted matrices in V are uniform. Then by Lemma 1, X ≈ ε 4 T ⊗ V ⊗ T . By Lemma 19, there is a nitely presented set Y , such that V ≈ ε 4 Y . Then by Lemma 1, X ≈ ε 2 T ⊗ Y ⊗ T . Finally, by Lemma 12, there is Z nitely presented such that T ⊗Y ⊗T ≈ ε 2 Z. We conclude by Lemma 1 that X ≈ ε Z.

C The reduction

Lemma 21 (Lemma 8 in the abstract). There are (n + 2, n + 2)-matrices (C p,q ) p,q∈G over R + and vectors I g and T g such that for all p 1 , q 1 , . . . , p k , q k ∈ Q g ,

∞ if p 0 ∈ I g , q 0 = p 1 , . . . , q k-1 = p k and q k ∈ T g , 0 otherwise. This is implemented in matrix form as follows. For each p, q where p, q ∈ Q g , set the matrix C p,q that has indices in Q g ∪ {i, ⊥}, to be such that:

0 if p = i, p ∈ I g and q = q, 0 if p = i, p ∈ I g and q = ⊥, 0 if p = p and q = q, 0 if p = i and p = p and q = ⊥, ∞ otherwise.

Dene furthermore I C be the vector with all entries ∞ but i which if 0, and let T C be the vector with all entries equal to ∞ but T g (and i if there is an initial and nite state in g).


C Pelat

P Y Boëlle

D Levy Bruhl

F Carrat

T Blanchon

T Hanslik

Early estimates of 2009 pandemic influenza A(H1N1) virus activity in general practice in France: incidence of influenza-like illness and age distribution of reported cases C Turbelin (

In the end of August 2009, an unusually elevated level of influenza-like illness (ILI) activity was reported to the French Sentinel Network. We quantified the observed excess in ILI cases in France during summer 2009 and characterised age patterns in reported cases.

An excess of cases has been observed since 5 July, with a time increasing trend. The cumulated estimated excess number of ILI cases was 269,935 [179,585; 316,512], corresponding to 0.5% French population over the period. Compared to the same period in the past years, relative cumulated incidence was greater among young subjects and lower among subjects over 65 years old. Compared to past epidemics, the relative cumulated incidence was greater in children less than 5 years old. This excess of cases may reflect the current spread of the A(H1N1) virus in France, subject to the following limitations: estimates were based on clinical cases consulting a GP; large media coverage may have led to a non specific increase in consultation rates.

Background

By the end of August, an unusually elevated level of influenza-like illness (ILI) had been reported to the French Sentinel Network (FSN), an epidemiological surveillance system based on general practitioners (GPs) and operating since 1984 in France.

The objective of the present study was to quantify the excess in ILI cases in France during the 2009 summer and to examine age patterns in the reported cases using, for comparison, data reported to a long-running routine surveillance system.

Method

Sentinel network and estimation of ILI incidence

Sentinel GPs report ILI cases to the FSN in real time. The ILI case definition is sudden onset of fever (39°C or above) with myalgia and respiratory signs [START_REF] Carrat | Evaluation of clinical case definitions of influenza: detailed investigation of patients during the 1995-1996 epidemic in France[END_REF]. Weekly ILI incidence is estimated using the average number of ILI cases reported by GPs, and then extrapolated to national ILI incidence using the ratio of all French GPs to participating sentinel GPs [START_REF] Garnerin | The French Communicable Diseases Computer Network. A seven-year experiment[END_REF].

Characteristics of the GPs in the Sentinel Network are similar to those of all French GPs as regards the regional distribution, the proportion of GPs in rural practice and the type of practice [START_REF] Chauvin | Attitude of French general practitioners to the public health surveillance of communicable diseases[END_REF].

Expected and excess ILI cases

Starting on 1 June 2009, the expected ILI incidence was calculated for each week as the average of weekly ILI incidences reported in the preceding, current and following weeks in the period 1985 to 2008 [START_REF] Stroup | Detection of aberrations in the occurrence of notifiable diseases surveillance data[END_REF]. A 90% confidence interval was derived from the 5 th and 95 th percentiles of these values (Q 5 and Q 95 , respectively) for each week.

For a given week, an excess in ILI incidence was defined when the observed incidence was above Q 95 . The number of excess cases was calculated as the difference between the observed and expected incidences. The inferior bound (respectively superior bound) of this excess was calculated as the difference between the observed incidence and Q 95 (respectively

Q 5 ) .

Relative cumulated incidence according to age

Incidence according to age was determined by apportioning extrapolated cases according to the age distribution in reported cases, using the following age groups: <5 years, 5-17, 18-49, 50-64 and 65 years. However, it is difficult to compare directly these incidences with past epidemics as the A(H1N1) pandemic is still in its early phase. Therefore, we extracted the age pattern of reported cases by computing relative incidence rates as the ratio of incidence in an age group to incidence in the whole population. Relative incidences larger than 1 indicate that the corresponding age class experienced larger incidence than the population as a whole.

The relative cumulated incidence rates according to age of ILI cases were calculated for: a) the current period, b) the same weeks in the past years and c) the past seasonal epidemic periods, as determined by the FSN and d) the 1986-7 and 1988-9 seasonal epidemics during which influenza A(H1N1) virus was the predominant circulating influenza virus [START_REF] Denoeud | Predicting pneumonia and influenza mortality from morbidity data[END_REF].

Results

As shown in Figure 1 The median age of ILI reported cases was 26 years (range: 1-103 years), and 48% were male. Compared to weeks 28 to 37 of past years since 1985, age group-relative incidence rates of ILI between weeks 28 and 37 of 2009 were greater among subjects less than 18 years old and smaller in those older than 65 years (Figure 2A).

Compared to past epidemic periods and A(H1N1) epidemics, age group-relative incidence rates of ILI between weeks 28 and 37 of 2009 was higher among subjects less than 5 years of age and lower among subjects aged 5 to 17 years (Figure 2B).

Discussion

An excess of 270,000 ILI cases has been reported to the French Sentinel Network since 1 July 2009, with a specific age pattern, compared to cases usually reported at this time of year. Compared to the past seasonal epidemics, (including those with predominant A(H1N1) circulating), the excess in ILI cases was largest among children less than 5 years old.

In the past 24 years of surveillance, upper respiratory tract infections have been uncommon in summer, making the last weeks exceptional. Besides the pandemic influenza A(H1N1) virus, no unusual circulation of an infectious agent, nor seasonal influenza viruses have been reported in France since 1 June 2009 [START_REF]Institut de veille sanitaire (InVS)[END_REF]. The recent excess of ILI cases must therefore reflect the developing pandemic in France. Some pitfalls arise in the interpretation of this increasing incidence. First, cases reported by GPs are based on a clinical definition without virological confirmation. This case definition had positive predictive value for approximately 40% influenza virus infections in the past seasonal epidemics [START_REF] Carrat | Evaluation of clinical case definitions of influenza: detailed investigation of patients during the 1995-1996 epidemic in France[END_REF]. It has been in use for 25 years in the FSN, making it likely that it is currently well applied by GPs. To further improve specificity, we retained only cases in excess of the expected incidence at this time of year in the calculations. Second, the heavy media coverage of the pandemic may have increased the propensity to visit a GP in case of symptoms, leading to an upward bias in the number of excess ILI cases. The change in age pattern of patients consulting their GPs argues against a mere change in consultation frequency; however an age-specific change in propensity to consult may also lead to this change. Last, cases of 2009 pandemic influenza A(H1N1) virus infection with mild disease and/or not seeking care are not taken into account in the estimates. We did not change the case definition to include milder cases so that direct comparison with the past years was possible.

As reported in other countries, a relatively higher incidence of 2009 pandemic influenza A(H1N1) virus infection is observed in the young. In most reports, the increased incidence among young subjects could be ascribed to case finding and ascertainment, with more young people being tested, for example as part of outbreaks of influenza in schools [START_REF] Baker | Pandemic influenza A(H1N1)v in New Zealand: the experience from April to August 2009[END_REF][START_REF] Dawood | Emergence of a novel swine-origin influenza A (H1N1) virus in humans[END_REF][START_REF] Gilsdorf | on behalf of the working group pandemic influenza A(H1N1)v. Influenza A(H1N1)v in Germany: the first 10,000 cases[END_REF]. Cases seen by the sentinel network GPs may provide a better picture of what is happening in the population at large. Using the same definition as before makes it possible to compare the current situation with the past.

The data confirmed and quantified an epidemic of ILI that started during the recent summer months in France, and had never been observed in the previous 25 years, with an agespecific incidence different from previous epidemic periods. These preliminary data highlight the heavy burden of this ILI epidemic on small children, relatively to older persons. [START_REF]Surveillance for pediatric deaths associated with 2009 pandemic influenza A (H1N1) virus infection -United States, April-August 2009[END_REF].

  Cases of infection with the 2009 pandemic influenza A(H1N1) virus have been reported in France since May 2009, with first evidence of local secondary transmission in July 2009.

  , the current estimated ILI incidence has been in excess of expected incidences of ILI cases in France since week 28 of 2009 (6 to 12 July), with an increasing time trend. Weekly estimated excess of ILI cases (90% CI bounds are presented in brackets) increased from 6,805 [654; 10,076] cases in week 29, to 92,505 [72,563; 101,456] cases in week 37, the time of writing this article (Table). Overall, the cumulated excess number of ILI cases between week 28 and week 37 of 2009 was 269,935 [179,585; 316,512] (323,420 reported ILI cases minus the expected 53,485 over the period).

Acknowledgement

We want to thank all general practitioners of the French Sentinel Network.


Pierre Thierry

Amélie Vagner

Mélanie Fontaine

Mitigate and Assess risk from Volcanic Impact on Terrain and human Activities: the FP7 MIAVITA project

come

Mitigate and Assess risk from Volcanic Impact on Terrain and human Activities: the FP7 MIAVITA project. P. Thierry, A. Vagner, M. Fontaine and MIAVITA team Volcanic eruptions are one of the most impressive, violent and dramatic agents of change on Earth. Volcanic emissions (gas and ashes) can widely affect human health and disturb airtraffic and little is known about their impact on agriculture. Some phenomena constitute therefore a multi-level threat to human societies and environment. Nevertheless, soils fertility, amongst other characteristics, often attracts populations, which settle on volcanoes flanks, creating, by the conjunction of hazards and population, conditions to high risks areas. Assessing and managing multi-hazard and multi-risk at volcanoes require the combination and coordination of many capabilities and instrumental techniques, and involve expertise in many various fields such as volcanology, social sciences, physics, signal processing, data analysis, agriculture and telecommunications… It needs also a strong experience in crisis management.

In EU countries, volcanic risks assessment and management are tackled through scientific knowledge and monitoring, although there is still a need for integration between all risk management components. For international cooperation partner countries (ICPCs), the risk management depends on local situations but is often less favourable. Therefore, following UN International Strategy for Disaster Reduction recommendations and starting from shared existing knowledge and practices, the MIAVITA project aims at developing tools and integrated cost effective methodologies to mitigate risks from various hazards on active volcanoes (prevention, crisis management and resilience). Such methodology has been designed for ICPCs contexts but will be helpful for European stakeholders to improve their experience in volcanic risk management. The project multidisciplinary team gathers civil protection agencies (French -DGPCGC and Italian -DPC), scientific teams in earth sciences -BRGM (F), INGV (I), IST (P), University of Cambridge (UK), NILU (N), social sciences -CNRS (F), soil and agriculture -Hohenheim University (D), Information Technologies and telecommunications -INESC-ID (P) and an IT private company -KELL (I). The objectives are being reached through sharing/transfer of know-how, through scientific and technological developments, and through dissemination/training, and with the help of local scientists and stakeholders in Africa (Cameroon -MINIMIDT, Cape Verde -INMG) and in Asia (Indonesia -CVGHM, Philippines -PHIVOLCS). The scientific work focuses on: 1) Risk assessment methodology based on a multi-risk approach developed at Mt Cameroon by BRGM in cooperation with Cameroonian institutions and on a decision tool already applied by CVGHM at Merapi; 2) Cost efficient monitoring tools designed for poorly monitored volcanoes (satellite+gas analysis+volcano-seismology); 3) Improvement in terms of vulnerability assessment (people, buildings and agriculture); 4) Socio-economic surveys to enhance community resilience; 5) Integrated information system (data organisation and transfers, communications) taking advantage of GEONETCast initiative.

MIAVITA conceptual frame

One of the main outcomes of the project is the final book, or handbook, on MIAVITA's experience on volcanic threat assessment and management, designed to help decision makers and stakeholders involved in volcanic risk management to handle all its aspects: prevention, crisis management and resilience. Thanks to the contribution of all its partners through common thoughts and studies, the MIAVITA project constituted a good opportunity to identify a list of minimum standards relevant for risk management in any geographical, geological and socio-economic situation in the context of an active volcano. This work is based on the scientific state of the art and the shared experience of the different partners as well as on identified international best practices. In particular, the goal is that any country, whatever its economic level and even with low basic knowledge about volcanoes, can identify, with the help of this handbook, suggestions for tackling the situation (monitoring, preparedness, prevision and resilience). The principle is to present an overview of all needed information to help decision makers set up technical and organisational frame for integrated volcanic risk prevention and crisis management. Ideally, the handbook aims at constituting a bridge between the different stakeholders and Authorities involved in risk management and Scientists, improving interactions among them.

The MIAVITA project is financed by the European Commission under the 7th Framework Programme for Research and Technological Development, Area "Environment", Activity 6.1 "Climate Change, Pollution and Risks".