Hugo Gimbert
email: hugo.gimbert@labri.fr

Youssouf Oualhadj
email: youssouf.oualhadj@labri.fr

Probabilistic Automata on Finite Words: Decidable and Undecidable Problems

. About the Emptiness problem, we provide a new simple undecidability proof and prove that it is undecidable for automata with as few as two probabilistic transitions. The Value 1 Problem is the special case of the Isolation Problem when λ = 1 or λ = 0. The decidability of the Value 1 Problem was an open question. We show that the Value 1 Problem is undecidable. Moreover, we introduce a new class of probabilistic automata, ♯-acyclic automata, for which the Value 1 Problem is decidable.

Introduction

Probabilistic automata on finite words are a computation model introduced by Rabin [START_REF] Michael | Probabilistic automata[END_REF]. Like deterministic automata on finite words, a probabilistic automaton reads finite words from a finite alphabet A. Each time a new letter a ∈ A is read, a transition from the current state s ∈ Q to a new state t ∈ Q occur. In a deterministic automaton, t is a function of s and a. In a probabilistic automaton, a lottery determines the new state, according to transition probabilities which depend on the current state s and letter a.

Since the seminal paper of Rabin, probabilistic automata on finite words have been extensively studied, see [START_REF] Bukharaev | Probabilistic automata[END_REF] for a survey of 416 papers and books about probabilistic automata published in the 60s and 70s.

Quite surprisingly, relatively few algorithmic results are known about probabilistic automata on finite words and almost all of them are undecidability results. There are two main algorithmic problems for probabilistic automata on finite words: the Emptiness Problem and the Isolation Problem. The Emptiness Problem asks, given some probability 0 ≤ λ ≤ 1, whether there exists a word accepted with probability greater than λ, while the Isolation Problem asks whether there exist words whose acceptance probability is arbitrarily close to λ. Both these problems were shown undecidable, respectively by Paz [START_REF] Paz | Introduction to probabilistic automata[END_REF] and Bertoni [START_REF] Bertoni | The solution of problems relative to probabilistic automata in the frame of the formal languages theory[END_REF][START_REF] Bertoni | Some recursive unsolvable problems relating to isolated cutpoints in probabilistic automata[END_REF]. To our knowledge, most decidability results known for probabilistic automata on finite words are rather straightforward: they either apply to one-letter probabilistic automata, in other words Markov chains, or to problems where the probabilistic nature of the automaton is not taken into account. A notable exception is the decidability of language equality [START_REF] Tzeng | A polynomial-time algorithm for the equivalence of probabilistic automata[END_REF].

In contrast, several algorithmic results were proved for probabilistic automata on infinite words. The existence of an infinite word accepted with probability 1 is decidable [START_REF] Alur | Distinguishing tests for nondeterministic and probabilistic machines[END_REF]. For probabilistic Büchi automata [START_REF] Baier | On decision problems for probabilistic büchi automata[END_REF], the emptiness problem may be decidable or not depending on the acceptance condition. A class of probabilistic Büchi automata which recognize exactly ω-regular languages was presented in [START_REF] Chadha | Power of randomization in automata on infinite strings[END_REF]. In this paper, we only consider automata on finite words but several of our results seem to be extendable to probabilistic automata on infinite words.

Our contributions are the following. First, we provide in Section 2.1 a new proof for the undecidability of the Emptiness Problem.

Second, we strengthen the result of Paz: the Emptiness Problem is undecidable even for automata with as few as two probabilistic transitions (Proposition 4).

Third, we solve an open problem: Bertoni's result shows that for any fixed cut-point 0 < λ < 1, the Isolation Problem is undecidable. However, as stated by Bertoni himself, the proof seems hardly adaptable to the symmetric cases λ = 0 and λ = 1. We show that both these cases are undecidable as well, in other words the Value 1 Problem is undecidable (Theorem 4).

Fourth, we introduce a new class of probabilistic automata, ♯-acyclic automata, for which the Value 1 Problem is decidable (Theorem 5 in Section 4). To our opinion, this is the main contribution of the paper. Moreover, this result is a first step towards the design of classes of stochastic games with partial observation for which the value 1 problem is decidable.

These undecidability results show once again that probabilistic automata are very different from deterministic and non-deterministic automata on finite of infinite words, for which many algorithmic problems are known to be decidable (e.g. emptiness, universality, equivalence). Surprisingly maybe, we remark that several natural decision problems about deterministic and non-deterministic automata are undecidable as well (Corollaries 1 and 2).

Due to space restrictions most proofs are omitted, they can be found in [?].

1 Probabilistic Automata

A probability distribution on Q is a mapping δ ∈ [0, 1] Q such that s∈S δ(s) = 1.
The set {s ∈ Q | δ(s) > 0} is called the support of δ and denoted Supp(δ). For every non-empty subset S ⊆ Q, we denote δ S the uniform distribution on S defined by δ(q) = 0 if q ∈ S and δ(q) = 1 |S| if q ∈ S. We denote D(Q) the set of probability distributions on Q.

Formally, a probabilistic automaton is a tuple A = (Q, A, (M a ) a∈A , q 0 , F ), where Q is a finite set of states, A is the finite input alphabet, (M a ) a∈A are the transition matrices, q 0 is the initial state and F is the set of accepting states. For each letter a ∈ A, M a ∈ [0, 1] Q×Q defines transition probabilities: 0 ≤ M a (s, t) ≤ 1 is the probability to go from state s to state t when reading letter a. Of course, for every s ∈ S and a ∈ A, t∈S M a (s, t) = 1, in other word in the matrix M a , the line with index s is a probability distribution on Q.

Transition matrices define a natural action of A * on D(Q). For every word a ∈ A and δ ∈ D(S), we denote δ • a the probability distribution in D(Q) defined by (δ • a)(t) = s∈Q δ(s) • M a (s, t). This action extends naturally to words of

A * : ∀w ∈ A * , ∀a ∈ A, δ • (wa) = (δ • w) • a.
The computation of A on an input word w = a 0 . . . a n ∈ A * is the sequence

(δ 0 , δ 1 , . . . , δ n ) ∈ D(Q) n+1 of probability distributions over Q such that δ 0 = δ {q0} and for 0 ≤ i < n, δ i+1 = δ i • a i .
For every state q ∈ Q and for every set of states R ⊆ Q, we denote P A (q w -→ R) = r∈R (δ q • w)(r) the probability to reach the set R from state q when reading the word w.

Definition 1 (Value and acceptance probability). The acceptance probability of a word w ∈ A * by A is P A (w) = P A (q 0 w -→ F ). The value of A, denoted val(A), is the supremum acceptance probability: val(A) = sup w∈A * P A (w).

The Emptiness Problem

Rabin defined the language recognized by a probabilistic automaton as L A (λ) = {w ∈ A * | P A (w) ≥ λ}, where 0 ≤ λ ≤ 1 is called the cut-point. Hence, a canonical decision problem for probabilistic automata is: Problem 1 (Emptiness Problem) Given a probabilistic automaton A and 0 ≤ λ ≤ 1, decide whether there exists a word w such that P A (w) ≥ λ.

The Strict Emptiness Problem is defined the same way except the large inequality P A (w) ≥ λ is replaced by a strict inequality P A (w) > λ.

The special cases where λ = 0 and λ = 1 provide a link between probabilistic and non-deterministic automata on finite words. First, the Strict Emptiness Problem for λ = 0 reduces to the emptiness problem of non-deterministic automata, which is decidable in non-deterministic logarithmic space. Second, the Emptiness Problem for λ = 1 reduces to the universality problem for nondeterministic automata, which is PSPACE-complete [START_REF] Kozen | Lower bounds for natural proofs systems[END_REF]. The two other cases are trivial: the answer to the Emptiness Problem for λ = 0 is always yes and the answer to the Strict Emptiness Problem for λ = 1 is always no.

In the case where 0 < λ < 1, both the Emptiness and the Strict Emptiness Problems are undecidable, which was proved by Paz [START_REF] Paz | Introduction to probabilistic automata[END_REF]. The proof of Paz is a reduction from an undecidable problem about free context grammars. An alternative proof was given by Madani, Hanks and Condon [START_REF] Madani | On the undecidability of probabilistic planning and related stochastic optimization problems[END_REF], based on a reduction from the emptiness problem for two counter machines. Since Paz was focusing on expressiveness aspects of probabilistic automata rather than on algorithmic questions, his undecidability proof is spread on the whole book [START_REF] Paz | Introduction to probabilistic automata[END_REF], which makes it arguably hard to read. The proof of Madani et al. is easier to read but quite long and technical.

In the next section, we present a new simple undecidability proof of the Emptiness Problem.

New proof of undecidability

In this section we show the undecidability of the (Strict) Emptiness Problem for the cut-point 1 2 and for a restricted class of probabilistic automata called simple probabilistic automata: Definition 2 (Simple automata). A probabilistic automaton is called simple if every transition probability is in 0, 1 2 , 1 . The proof is based on a result of Bertoni [START_REF] Bertoni | The solution of problems relative to probabilistic automata in the frame of the formal languages theory[END_REF]: the undecidability of the Equality Problem.

Problem 2 (Equality problem) Given a simple probabilistic automaton A, decide whether there exists a word w ∈ A * such that P A (w) = 1 2 .

Proposition 1 (Bertoni). The equality problem is undecidable.

The short and elegant proof of Bertoni is a reduction of the Post Correspondence Problem (PCP) to the Equality Problem.

Problem 3 (PCP) Let ϕ 1 : A → {0, 1} * and ϕ 2 : A → {0, 1} * two functions, naturally extended to A * . Is there a word w ∈ A * such that ϕ 1 (w) = ϕ 2 (w)?

Roughly speaking, the proof of Proposition 1 consists in encoding the equality of two words in the decimals of transition probabilities of a well-chosen probabilistic automaton. While the reduction of PCP to the Equality problem is relatively well-known, it may be less known that there exists a simple reduction of the Equality problem to the Emptiness and Strict Emptiness problems: Proposition 2. Given a simple probabilistic automaton A, one can compute probabilistic automata B and C whose transition probabilities are multiple of 1 4 and such that:

∃w ∈ A + , P A (w) = 1 2 ⇐⇒ ∃w ∈ A + , P B (w) ≥ 1 4 (1)
⇐⇒ ∃w ∈ A + , P C (w) > 1 8 . ( 2
)
Proof. The construction of B such that (1) holds is based on a very simple fact: a real number x is equal to 1 2 if and only if x(1-x) ≥ 1 4 . Consider the automaton B which is the cartesian product of A with a copy of A whose accepting states are the non accepting states of A. Then for every word w ∈ A * , P A1 (w) = P A (w)(1 -P A (w)), thus (1) holds.

The construction of C such that (2) holds is based on the following idea. Since A is simple, transition probabilities of B are multiples of 1 4 , thus for every word w of length |w|, P B (w) is a multiple of

(aw) = 1 2 • P B (w) + 1 2 • 1 4 |w| , thus (2)
holds. To build C, simply add a new initial state that goes with equal probability 1 2 either to the initial state of B or to a new accepting state q f . From q f , whatever letter is read, next state is q f with probability 1 4 and with probability 3 4 it is a new non-accepting absorbing sink state q * . ⊓ ⊔

As a consequence:

Theorem 1 (Paz). The emptiness and the strict emptiness problems are undecidable for probabilistic automata. These problems are undecidable even for simple probabilistic automata and cut-point λ = 1 2 .

To conclude this section, we present another connection between probabilistic and non-probabilistic automata on finite words.

Corollary 1. The following problem is undecidable. Given a non-deterministic automaton on finite words, does there exists a word such that at least half of the computations on this word are accepting?

We do not know a simple undecidability proof for this problem which does not make of use of probabilistic automata.

Probabilistic automata with few probabilistic transitions

Hirvensalo [START_REF] Hirvensalo | Improved undecidability results on the emptiness problem of probabilistic and quantum cut-point languages[END_REF] showed that the emptiness problem is undecidable for probabilistic automata which have as few as 2 input letters and 25 states, see also [START_REF] Blondel | Undecidable problems for probabilistic automata of fixed dimension[END_REF] for similar result about the isolation problem.

On the other hand, the emptiness problem is decidable for deterministic automata. This holds whatever the number of states, as long as there are no probabilistic transition in the automaton. Formally, a probabilistic transition is a couple (s, a) of a state s ∈ S and a letter a ∈ A such that for at least one state t ∈ S, 0 < M a (s, t) < 1.

This motivates the following question: what is the minimal number of probabilistic transitions for which the emptiness problem is undecidable?

The following undecidability result is a rather surprising answer:

Proposition 3. The emptiness problem is undecidable for probabilistic automata with two probabilistic transitions.

Moreover, a slight variant of the emptiness problem for probabilistic automata with one probabilistic transition is undecidable: Proposition 4. The following problem is undecidable: given a simple probabilistic automaton over an alphabet A with one probabilistic transition and given a rational language of finite words L ⊆ A * , decide whether P A (w) ≥ 1 2 for some word w ∈ L.

For probabilistic automata with a unique probabilistic transition, we do not know whether the emptiness problem is decidable or not.

Undecidability of the Value 1 problem

In his seminal paper about probabilistic automata [START_REF] Michael | Probabilistic automata[END_REF], Rabin introduced the notion of isolated cut-points.

Definition 3. A real number 0 ≤ λ ≤ 1 is an isolated cut-point with respect to a probabilistic automaton A if: ∃ε > 0, ∀w ∈ A * , |P A (w) -λ| ≥ ε .
Rabin motivates the introduction of this notion by the following theorem:

Theorem 2 (Rabin). Let A a probabilistic automaton and 0 ≤ λ ≤ 1 a cut- point. If λ is isolated then the language L A (λ) = {u ∈ A * | P A (u) ≥ λ} is rational.
This result suggests the following decision problem.

Problem 4 (Isolation Problem) Given a probabilistic automaton A and a cut-point 0 ≤ λ ≤ 1, decide whether λ is isolated with respect to A.

Bertoni [START_REF] Bertoni | The solution of problems relative to probabilistic automata in the frame of the formal languages theory[END_REF] proved that the Isolation Problem is undecidable in general: Theorem 3 (Bertoni). The Isolation Problem is undecidable for probabilistic automata with five states.

A closer look at the proof of Bertoni shows that the Isolation Problem is undecidable for a fixed λ, provided that 0 < λ < 1.

However the same proof does not seem to be extendable to the cases λ = 0 and λ = 1. This was pointed out by Bertoni in the conclusion of [START_REF] Bertoni | The solution of problems relative to probabilistic automata in the frame of the formal languages theory[END_REF]: "Is the following problem solvable: ∃δ > 0, ∀x, (p(x) > δ)? For automata with 1-symbol alphabet, there is a decision algorithm bound with the concept of transient state [START_REF] Paz | Introduction to probabilistic automata[END_REF]. We believe it might be extended but have no proof for it".

The open question mentioned by Bertoni is the Isolation Problem for λ = 0. The case λ = 1 is essentially the same, since 0 is isolated in an automaton A if and only if 1 is isolated in the automaton obtained from A by turning final states to non-final states and vice-versa. When λ = 1, the Isolation Problem asks whether there exists some word accepted by the automaton with probability arbitrarily close to 1. We use the game-theoretic terminology and call this problem the Value 1 Problem.

The open question of Bertoni can be rephrased as the decidability of the following problem: The proof of Theorem 4 relies on the fact that there is a natural way to combine A x with an arbitrary automaton B so that the resulting automaton has value 1 if and only if some word is accepted by B with probability strictly greater than The value 1 problem for simple probabilistic automata can be straigntforwardly rephrased as a "quantitative" decision problem about non-deterministic automaton on finite words, which shows that:

Corollary 2. This decision problem is undecidable: given a non-deterministic automaton on finite words, does there exists words such that the proportion of of non-accepting computation pathes among all computation pathes is arbitrarily small?

In this section, we introduce a new class of probabilistic automata, ♯-acyclic probabilistic automata, for which the value 1 problem is decidable.

To get a decision algorithm for the value 1 problem, our starting point is the usual subset construction for non-deterministic automata, defined by mean of the natural action of letters on subsets of Q. However the quantitative aspect of the Value 1 Problem stressed in Corollary 2 suggests that the subset construction needs to be customized. Precisely, we use not only the usual action S • a of a letter a on a subset S ⊆ Q of states but consider also another action a ♯ . Roughly speaking, a ♯ deletes states that are transient when reading letter a forever.

Definition 4 (Actions of letters and ♯-reachability).

Let A a probabilistic automaton with alphabet A and set of states Q. Given S ⊆ Q and a ∈ A, we denote:

S • a = {s ∈ Q | ∃s ∈ S, M a (s, t) > 0} . A state t ∈ Q is a-reachable from s ∈ Q if for some n ∈ N, P A (s a n --→ t) > 0. A state s ∈ Q is a-recurrent if it

is in a bottom strongly connected component of the graph of states and a-transitions i.e. if for any state

t ∈ Q, (t is a-reachable from s) =⇒ (s is a-reachable from t) . A set S ⊆ Q is a-stable if S = S • a. If S is a-stable, we denote: S • a ♯ = {s ∈ S | s is a-recurrent} .
The support graph G A of a probabilistic automaton A with alphabet A and set of states Q is the directed graph whose vertices are the non-empty subsets of Q and whose edges are the pairs (S, T ) such that for some letter a ∈ A, either (S • a = T ) or (S • a = S and S • a ♯ = T ).

Reachability in the support graph of A is called ♯-reachability in A.

The class of ♯-acyclic probabilistic automata is defined as follows.

Definition 5 (♯-acyclic probabilistic automata). A probabilistic automaton is ♯-acyclic if the only cycles in its support graph are self-loops.

Obviously, this acyclicity condition is quite strong. However, it does not forbid the existence of cycles in the transition table, see for example the automaton depicted on Fig. 2. Note also that the class of ♯-acyclic automata enjoys good properties: it is closed under cartesian product and parallel composition.

The value 1 problem is decidable for ♯-acyclic automata

For ♯-acyclic probabilistic automata, the value 1 problem is decidable: Theorem 5. Let A be a probabilistic automaton with initial state q 0 and final states F . Suppose that A is ♯-acyclic . Then A has value

1 if and only if F is ♯-reachable from {q 0 } in A.
The support graph can be computed on the fly in polynomial space thus deciding whether a probabilistic automaton is ♯-acyclic and whether an ♯-acyclic automaton has value 1 are PSPACE decision problems.

The rest of this section is dedicated to the proof of Theorem 5. This proof relies on the notion of limit-paths. Definition 6 (Limit paths and limit-reachability). Let A be a probabilistic automaton with states Q and alphabet A. Given two subsets S, T of Q, we say that T is limit-reachable from S in A if there exists a sequence w 0 , w 1 , w 2 , . . . ∈ A * of finite words such that for every state s ∈ S:

P A (s wn --→ T ) ----→ n→∞ 1 .
The sequence w 0 , w 1 , w 2 , . . . is called a limit path from S to T , and T is said to be limit-reachable from S in A.

In particular, an automaton has value 1 is and only if F is limit-reachable from {q 0 }.

To prove Theorem 5, we show that in ♯-acyclic automata, ♯-reachability and limit-reachability coincide. The following proposition shows that ♯-reachability always imply limit-reachability, may the automaton be ♯-acyclic or not. Proposition 6. Let A be a probabilistic automaton with states Q and S, T ⊆ Q.

If T is ♯-reachable from S in A then T is limit-reachable from S in A.
The converse implication is not true in general. For example, consider the automaton depicted on Fig. 3. There is only one final state, state 3. The initial state is not represented, it leads with equal probability to states 1, 2 and 3. The transitions from states 1, 2 and 3 are either deterministic or have probability 1 2 . It turns out that the automaton on Fig. 3 has value 1, because ((b n a) n ) n∈N is a limit-path from {1, 2, 3} to {3}. However, {3} is not reachable from {1, 2, 3} in the support graph. Thus, limit-reachability does not imply ♯-reachability in general. This automaton is not ♯-acyclic , because his support graph contains a cycle of length 2 between {1, 2, 3} and {1, 3}. It is quite tempting to add an edge labelled (ab ♯ ) ♯ between {1, 3} and {3}. Now we prove that for ♯-acyclic automata, limit-reachability implies ♯-reachability.

Definition 7 (Stability and ♯-stability). Let A be a probabilistic automaton with states Q. The automaton A is stable if for every letter a ∈ A, Q is a-stable.

A stable automaton A is ♯-stable if for every letter a ∈ A Q • a ♯ = Q.
The proof relies on the three following lemmatas.

Lemma 1 (Blowing lemma). Let A be a ♯-acyclic probabilistic automaton with states Q and S ⊆ Q. Suppose that A is ♯-acyclic and ♯-stable.

If Q is limit-reachable from S in A, then Q is ♯-reachable from S as well.
Proof (of the blowing lemma). If S = Q there is nothing to prove. If S = Q, we prove that there exists S 1 ⊆ Q such that (i) S 1 is ♯-reachable from S, (ii) S S 1 , and (iii) Q is limit-reachable from S 1 . Since S Q and since there exists a limit-path from S to Q there exists at least one letter a such that S is not a-stable, i.e. S • a ⊆ S. Since A is subset-acyclic, there exists n ∈ N such that S • a n+1 = S • a n i.e. S • a n is a-stable. We choose S 1 = (S • a n ) • a ♯ and prove (i),(ii) and (iii) First, (i) is obvious.

To prove (ii), we prove that S 1 contains both S and S • a. Let s ∈ S. By definition, every state t of S • a n is a-accessible from s. Since A is ♯-stable, state s is a-recurrent and by definition of a-recurrence, s is a-accessible from t. Since t ∈ S • a n and S • a n is a-stable, s ∈ S • a n and since s is a-recurrent s ∈ (S • a n ) • a ♯ = S 1 . The proof that S • a ⊆ S 1 is similar.

If S 1 = Q the proof is complete, because (i) holds. If S 1 Q, then (iii) holds because S ⊆ S 1 thus Q is limit-reachable not only from S but from S 1 as well, using the same limit-path. As long as S n = Q, we use (iii) to build inductively an increasing sequence S S 1 S 2 . . . S n = Q such that for every 1 ≤ k < n, S k+1 is ♯-reachable from S k . Since ♯-reachability is transitive this completes the proof of the blowing lemma.

⊓ ⊔

Next lemma shows that in a ♯-stable and ♯-acyclic automata, once a computation has flooded the whole state space, it cannot shrink back.

Lemma 2 (Flooding lemma). Let A be a probabilistic automaton with states Q. Suppose that A is ♯-acyclic and ♯-stable. Then Q is the only set of states limit-reachable from Q in A. Now, we turn our attention to leaves of the acyclic support graph.

Definition 8. Let A be a probabilistic automaton with states

Q. A non-empty subset R ⊆ Q is called a leaf if for every letter a ∈ A, R • a = R and R • a ♯ = R.
In a stable ♯-acyclic automaton, there is a unique leaf: Lemma 3 (Leaf lemma). Let A be a probabilistic automaton with states Q. Suppose that A is ♯-acyclic .Then there exists a unique leaf ♯-accessible from Q. Every set limit-reachable from Q contains this leaf.

To prove that limit-reachability implies ♯-reachability, we proceed by induction on the depth in the support graph. The inductive step is: Lemma 4 (Inductive step). Let A be a probabilistic automaton with states Q and S 0 , T ⊆ Q. Suppose that A is ♯-acyclic and T is limit-reachable from S 0 . Then either S 0 = T or there exists S 1 = S 0 such that S 1 is ♯-reachable from S 0 in A and T is limit-reachable from S 1 in A.

Repeated use of Lemma 4 gives:

Proposition 7. Let A be a probabilistic automaton with states Q and S 0 , T ⊆ Q. Suppose that A is ♯-acyclic. If T is limit-reachable from S 0 in A, then T is ♯-reachable from S 0 as well. Proof. To prove Proposition 4, we provide an algorithm which takes as input a simple probabilistic automaton A on an alphabet A (with an arbitrary number of probabilistic transitions) and outputs two objects:

• a simple automaton A ′ over an alphabet A ′ with only one probabilistic transition and • |A| words {u a , a ∈ A} on the alphabet A ′ , each word u a of length 3|Q|, such that:

∃w ∈ A * , P A (w) ≥ 1 2 ⇐⇒ ∃w ∈ {u a , a ∈ A} * , P A ′ (w ′ ) ≥ 1 2 . ( 6
)
According to Theorem 1, the Emptiness Problem for simple probabilistic automata and cut-point 1 2 is undecidable, hence (6) proves Proposition 4. The alphabet A ′ , the automaton A ′ and the words (u a ) a∈A are defined as follows. If A = (Q, A, M, q 0 , F ) then A ′ = (Q ′ , A ′ , M ′ , q 0 , F ) is defined by: 1. The alphabet A ′ is made of a new letter a * plus, for each letter a ∈ A and state s ∈ Q, two new letters α(a, s) and β(a, s) so that:

A ′ = {a * } ∪ a∈A,s∈Q
{α(a, s), β(a, s)} .

2. The set of states of A ′ is obtained from Q by addition of three new states s * , s 0 , s 1 , so that: Q ′ = Q ∪ {s * , s 0 , s 1 } . 3. The initial state q 0 and the set of final states F are left unchanged. 4. The transitions of A ′ are as follows. For every letter a ∈ A and state s ∈ Q, the new letter α(a, s) has no effect on states u = s (i.e. M α(a,s) (u) = u), while from state s the transition is deterministic to state s * i.e. M α(a,s) (s) = s * . 5. The new letter a * has no effect on states u = s * , while from state s * this is the only probabilistic transition of A ′ , defined by M a * (s * ) = 1 2 s 0 + 1 2 s 1 . 6. For every letter a ∈ A and state s ∈ Q, the new letter β(a, s) has no effect on states u ∈ {s 0 , s 1 }. Transitions on letter β(a, s) from states s 0 and s 1 are deterministic and depend on M a (s). If the transition M a (s) is deterministic, i.e. if M a (s, r) = 1 for some state r then M β(a,s) (s 0 ) = r and M β(a,s) (s 1 ) = r.

If the transition M a (s) is probabilistic i.e. if M a (s) = 1 2 r+ 1 2 r ′ for some states r, r ′ then M β(a,s) (s 0 ) = r and M β(a,s) (s 1 ) = r ′ . Now we define the words u a , a ∈ A. Choose some enumeration {s 0 , s 1 , . . . , s n } = Q of states of A and for each letter a, define the word u a = α(a, s 0 )a * β(a, s 0 )α(a, s 1 )a * β(a, s 1 ) • • • α(a, s n )a * β(a, s n ) ∈ A ′ * . Then (6) holds because for every word a 0 a 1 a 2 • • • ∈ A * , P A (a 0 a 1 a 2 • • • ) = P A ′ (u a0 u a1 u a2 . . .) .

Since automaton A ′ has only one probabilistic transition, this completes the proof of Proposition 4.

⊓ ⊔

Problem 5 (Theorem 4 .

 54 Value 1 Problem) Given a probabilistic automaton A, decide whether A has value 1. Unfortunately, The Value 1 Problem is undecidable. The proof of Theorem 4 is a reduction of the Strict Emptiness Problem to the Value 1 Problem. It is similar to the proof of undecidability of the Emptiness Problem for probabilistic Büchi automata of Baier et al. [2]. The core of the proof is the following proposition. Proposition 5. Let 0 < x < 1 and A x be the probabilistic automaton depicted on Fig. 1. Then A x has value 1 if and only if x > 1 2 .

Fig. 1 .

 1 Fig.1. This automaton has value 1 if and only if x >1 2 .

Fig. 2 .

 2 Fig.2. A ♯-acyclic automaton (on the left) and its support graph (on the right). All transition probabilities are equal to1 2 .

Fig. 3 .

 3 Fig.3. This automaton has value 1 and is not ♯-acyclic .

  1 4 |w| . As a consequence, P B (w) ≥1 4 if and only if P B (w) > 1 4 -1 4 |w| . Adding three states to B, one obtains easily a probabilistic automaton C such that for every non-empty word w ∈ A * and letter a ∈ A, P C

Acknowledgments We thank the anonymous referees as well as A. Muscholl and I. Walukiewicz for finding a flaw in the previous version of this manuscript. We thank Benedikt Bollig for his valuable comments during the final preparation of this manuscript.

Thus, limit-reachability and ♯-reachability coincide in ♯-acyclic automata and Theorem 5 holds.

Is the maximal distance between two ♯-reachable sets in the support graph bounded by a polynomial function of |A| and |Q|? The answer to this question could lead to a simpler proof and/or algorithm.

Conclusion

Whether the emptiness problem is decidable for probabilistic automata with a unique probabilistic transition is an open question.

The class of ♯-acyclic automata can be probably extended to a larger class of automata for which the value 1 problem is still decidable.

Appendix

Proof (of Proposition 1). Given any instance ϕ 1 , ϕ 2 : A → {0, 1} * of the PCP problem, we build an automaton A which accepts some word with probability 1 2 if and only if PCP has a solution. Let ψ : {0, 1} * → [0, 1] the mapping defined by:

and let θ 1 = ψ • ϕ 1 and θ 2 = ψ • ϕ 2 . Without loss of generality, by insertion of 1's in words of the PCP instance, we can suppose that ϕ 1 , ϕ 2 : A → {10, 11} * . That way, since Φ is injective on 1{0, 1} * :

Let A 1 = (Q, A, M, q 1 0 , q 1 F ) the probabilistic automaton with two states Q = {q 1 0 , q 1 F } and transitions:

A simple computation shows that:

A very similar construction produces a two-states automaton A 2 such that:

Let A be the disjoint union of these two automata A 1 and A 2 plus a new initial state that leads with equal probability 1 2 to one of the initial states q 1 0 and q 2 0 of A 1 and A 2 . Then for every word w ∈ A * and every letter a ∈ A,

where the first equivalence is by definition of A, the second is by ( 4) and ( 5), the third holds by (3) and the fourth is by definition of PCP. This completes the proof of Proposition 1.

⊓ ⊔

Proof (of Theorem 1). According to Proposition 1 and Proposition 2 the emptiness and the strict emptiness problems are undecidable for cut-point 1 2 and automata whose transition probabilities are multiples of 1 8 . The transformation of such automata into simple automata is easy.

Proof. The undecidable problem described in Proposition 4 reduces to the emptiness problem for simple probabilistic automata with two probabilistic transitions: given A and L, add a new initial state to A and from this new initial state, proceed with probability 1 2 either to the original initial state of A to the initial state of a deterministic automaton that checks whether the input word is in L. This new automaton accepts a word with probability more than 3 4 if and only if the original automaton accepts a word with probability more than 1 2 . ⊓ ⊔ 7 Proof of Proposition 5

Proof (of Proposition 5). We shall prove:

In order to prove this equivalence we notice that: P Ax (1

) k∈N an increasing sequence of integers. By reading the word w = a n0 ba n1 b . . . a ni b, we get:

no word w can be accepted with probability greater than 1 2 , in particular the automaton does not have value 1. This proves the converse implication in [START_REF] Chadha | Power of randomization in automata on infinite strings[END_REF]. Assume that x > 1 2 and let ε > 0, we exhibit an increasing sequence of integers (n k ) k∈N such that we have:

In the other hand we have:

There exists β > 1 such that:

Since this series converges, we satisfy [START_REF] Chadha | Power of randomization in automata on infinite strings[END_REF] by choosing a suitable constant c.

Suppose now that ( 7) is satisfied for some sequence n 0 , n 1 , n 2 . . .. Then according to [START_REF] Hirvensalo | Improved undecidability results on the emptiness problem of probabilistic and quantum cut-point languages[END_REF], for every i ∈ N the word a n0 ba n1 b . . . a ni b is accepted by A x with probability

According to , when i goes to ∞, the left operand converges to 1 2 and the right operand is asymptotically larger than 1 2 (1-ε). This proves the implication in [START_REF] Chadha | Power of randomization in automata on infinite strings[END_REF]. ⊓ ⊔

8 Proof of Theorem 4

Proof (of Theorem 4). Given a probabilistic automaton B with alphabet A such that a, b ∈ B, we combine B and the automaton A x on Fig. 1 to obtain an automaton C which has value 1 if and only if there exists a word w such that

C is computed as follows. First, the transitions in A x on letter a are deleted. Second, we make two copies A 4 and A 1 of the automaton B, such that the initial state of A 4 is 4 and the initial state of A 1 is 1. From states of A 4 and A 1 other than the initial states, reading letter b leads to the sink state 6. Third, from a state s of A 4 the transition on the new letter ♯ is deterministic and leads to 5 if s is a final state and to 4 if s is not a final state. Fourth, from a state s of A 1 the transition on the new letter ♯ is deterministic and leads to 1 if s is a final state and to 2 if s is not a final state. Fifth, the final states of C are 5 and 3. Sixth, states 0, 3, 6, 5 and 2 are absorbing for letters in A.

Then suppose there exists w such that P A (w) > 1 2 and let us show that C has value 1. Let ǫ > 0 and let u ǫ = ba i0 ba i1 ba i2 b • • • a i k be a word accepted by B with probability 1ǫ. Then by construction of C,

Now suppose that for every w ∈ A * , P A w ≤ 1 2 and let us show that C has not value 1. Let

Then by construction of C and by hypothesis,

2 ). Thus val(C) ≤ val(A 1 2 ) and according to Proposition 5, val(C) < 1.

⊓ ⊔ 9 Proof of Theorem 5

Proof (of Proposition 6). Proposition 6 is a consequence of the two following facts. First, if there is an edge from S to T in the support graph of A, then T is limit reachable from S: let S, T ⊆ Q and a ∈ A. If S • a = T , then the sequence constant equal to a is a limit path from S to T . If S • a = S and S • a ♯ = T then by definition of S • a ♯ , (a n ) n∈N is a limit path from S to T .

Second, limit-reachability is a transitive relation: let S 0 , S 1 , S 2 ⊆ Q such that S 1 is limit-reachable from S 0 and S 2 is limit-reachable from S 1 . Let (u n ) n∈N a limit-path from S 0 to S 1 and (v n ) n∈N a limit-path from S 1 to S 2 . Then (u n v n ) n∈N is a limit-path from S 0 to S 2 .

⊓ ⊔ Proof (of the leaf lemma). Since A is ♯-acyclic , there exists at least one leaf S which is ♯-reachable from Q. We prove that every set limit-reachable from Q contains the leaf S. Let R limit-reachable from Q and (u n ) n∈N a limit-path from Q to R. Since S is a leaf then for every a ∈ A, S is a-stable, hence (u n ) n∈N is a fortiori a limit-path from S to R ∩ S. Since S is a leaf, the restriction A[S] of the automaton A to S is ♯-stable. According to the flooding lemma applied to A[S], S = R ∩ S, thus S ⊆ R. Since ♯-reachability imply limit-reachability, this implies unicity of the leaf reachable from Q.

⊓ ⊔ Proof (of the Flooding lemma). Let (u n ) n∈N be a limit path from Q to some set of states T Q. We shall prove that

First, we prove that for every letter a ∈ A T , Q\T is a-stable. Otherwise there would be s ∈ Q \ T , a ∈ A T and t ∈ T such that t is a-reachable from s. Since A is ♯-stable, s and t are both a-recurrent, and by definition of a-recurrence, since t is a-reachable from s, s would be a-reachable from t as well. But s ∈ Q \ T and t ∈ T , which contradicts the a-stability of T .

Second, we prove that u n ∈ A * T for only finitely many n ∈ N. Since for every a ∈ A T , Q \ T is a-stable, then during the computation δ Q = δ 0 , δ 1 , . . . , δ |un| on the word u n , s∈Q\T δ k (s) is constant. Thus, for every n ∈ N,

Since (u n ) n∈N is a limit-path from Q to T , P A (s un --→ T ) converges to 0 hence the inequality can hold only for finitely many n ∈ N. Now we show that there exists T 1 ⊆ Q such that:

Since any infinite subsequence of a limit-path is a limit-path, and since we proved that u n ∈ A * T for only finitely many n ∈ N, we can assume w.l.o.g. that for every n ∈ N, u n ∈ A * T . Thus for every n ∈ N, there exists

The choice of T 1 such that (i), (ii) and (iii) hold depends on Supp(δ) • a.

If Supp(δ) • a = T then we choose T 1 = Supp(δ). Then (i) holds because a ∈ A T , (ii) holds because T = T 1 • a and (iii) holds because (v n ) n∈N is a limit-path from Q to T 1 .

If Supp(δ) • a = T then we choose T 1 = Supp(δ) • a. Then (i) clearly holds and (iii) holds because (v n a) n∈N is a limit path from Q to T 1 in A. To prove that (ii) holds, consider the restriction A[T, A T ] of automaton A to states T and alphabet A T . Then (w n ) n∈N is a limit-path from T 1 to T in A[T, A T ]. Moreover, since A is ♯-acyclic and ♯-stable, A[T, A T ] also is. Thus, we can apply the blowing lemma to A[T, A T ] and T 1 , which proves that T is ♯-reachable from T 1 in A[T, A T ], thus in A as well.

If T 1 = Q, the proof is complete. Otherwise, as long as T n = Q, we use condition (iii) to build inductively a sequence

Since ♯-reachability is transitive, this proves that T is ♯-reachable from Q. Since A is ♯-stable, the only set ♯-reachable from Q is Q thus T = Q, which completes the proof of the Flooding lemma.

⊓ ⊔ Proof (of Lemma 4). Let (u n ) n∈N be a limit-path from S 0 to T . Let A 0 = {a ∈ A | S 0 • a = S 0 }. For every n ∈ N, let v n be the longuest prefix of u n in A * 0 . Since every infinite subsequence of a limit-path is a limit-path, and since D(Q) is compact, we can suppose without loss of generality that (δ

Suppose first that Supp(δ) = S 0 . If u n ∈ A * 0 for infinitely many n ∈ N then T = S 0 . Otherwise, since A is finite we can suppose w.l.o.g. that there exists a letter a ∈ A \ A 0 such that for every n ∈ N, v n a is a prefix of u n . Let also w n such that u n = v n aw n . Let S 1 = S 0 • a. Then S 1 = S 0 because a ∈ A 0 and S 1 is clearly ♯-reachable from S 0 . Moreover (w n ) n∈N is a limit-path from S 1 to T , this completes the proof.

Suppose now that Supp(δ) = S 0 . Let A[S 0 , A 0 ] the probabilistic automaton obtained from A by restriction to the alphabet A 0 and to the state space S 0 . By definition of A 0 , A[S 0 , A 0 ] is stable and it is ♯-acyclic because A is. According to the leaf lemma, A[S 0 , A 0 ] has a unique leaf. Let S 1 be this unique leaf. Since Supp(δ) is limit-reachable from S 0 in A[S 0 , A 0 ], according to the leaf lemma again, S 1 ⊆ Supp(δ) hence S 1 = S 0 . Moreover, since it is the unique leaf, S 1 is ♯-reachable from S 0 in A[S 0 , A 0 ] hence in A as well. For every n ∈ N, let w n such that u n = v n w n . Then (w n ) n∈N is a limit-path from S 1 to T . This completes the proof.

⊓ ⊔ Proof (of Proposition 7). Apply again and again Lemma 4 to build a sequence S 0 , S 1 , S 2 , . . . such that for every k, S k = S k+1 , S k+1 is ♯-reachable from S k and T is limit-reachable from S k+1 . As long as S k = T , Lemma 4 is used to build S k+1 . Since A is subset-acyclic, the sequence has length at most 2 Q thus for some k, S k = T . Since ♯-reachability is transitive, this proves that T is ♯reachable from S 0 . ⊓ ⊔


Emilie Franceschini

François T H Yu

François Destrempes

Guy Cloutier

Ultrasound characterization of red blood cell aggregation with intervening attenuating tissue-mimicking phantoms

Keywords: numbers: 43.35.Bf 43.35.Yb 43.80.Cs 43.80.Ev attenuation, ultrasound backscatter, blood, ultrasound tissue characterization

The analysis of the ultrasonic frequency-dependent backscatter coefficient of aggregating red blood cells reveals information about blood structural properties. The difficulty in applying this technique in vivo is due to the frequency-dependent attenuation caused by intervening tissue layers that distorts the spectral content of signals backscattered by blood. An optimization method is proposed to simultaneously estimate tissue attenuation and blood structure properties, and was termed the Structure Factor Size and Attenuation Estimator (SFSAE). An ultrasound scanner equipped with a wide-band 25 MHz probe was used to insonify porcine blood sheared in both Couette and tubular flow devices. Since skin is one of the most attenuating tissue layers during in vivo scanning, four skin-mimicking phantoms with different attenuation coefficients were introduced between the transducer and the blood flow. The SFSAE gave estimates with relative errors below 25% for attenuations between 0.115 and 0.411 dB/MHz and kR <2.08 (k being the wave number and R the aggregate radius). The SFSAE can be useful to examine in vivo and in situ abnormal blood conditions suspected to promote pathophysiological cardiovascular consequences.

I. INTRODUCTION

Ultrasonic tissue characterization techniques using the radio frequency (RF) backscattered signals have received broad interest for the past 25 years. One approach is to use the magnitude and frequency dependence of the RF backscatter spectrum in order to quantify the tissue structures such as the size, acoustic impedance, and concentration of the scatterers. Many in vitro and in vivo experiments have been performed to demonstrate the utility of this approach for characterizing the eye 1,2 , liver [START_REF] Lizzi | Relationship of ultrasonic spectral parameters to features of tissue microstructure[END_REF] , kidney [START_REF] Insana | Identifying acoustic scattering sources in normal renal parenchyma in vivo by varying arterial and ureteral pressures[END_REF] , prostate [START_REF] Feleppa | Ultrasonic spectral-parameter imaging of the prostate[END_REF] and breast [START_REF] Oelze | Differentiation and characterization of rat mammary fibroadenomas and 4T1 mouse carcinomas using quantitative ultrasound imaging[END_REF] . Recently, the frequency dependence of the ultrasound (US) backscatter coefficient was studied to assess the level of red blood cell (RBC) aggregation. [START_REF] Yu | Experimental ultrasound characterization of red blood cell aggregation using the structure factor size estimator[END_REF] It is well known that when RBCs are under low shear rates (<10 s -1 ), they interact strongly with each other and form complex three-dimensional rouleaux structures. When the shear rate increases, rouleaux structures desaggregate. This phenomenon is normal and occurs in the circulation of many mammalian species. However, RBC hyper-aggregation, an abnormal increase of RBCs aggregation, is a pathological state associated with several circulatory diseases such as deep venous thrombosis, atherosclerosis and diabetes mellitus. These pathologies inflict particular sites (inferior members for thrombosis, arterial bifurcations for atherosclerosis, the foot and eye for diabetes). It would thus be of great interest to elucidate the role of flow-dependent rheological parameters, such as RBC aggregation, in the etiology of these pathologies in vivo and in situ with US techniques. To achieve this goal, the backscattering coefficient from blood was parametrized: two indices describing RBC aggregation, the packing factor and mean aggregate diameter, were extracted from the Structure Factor Size Estimator (SFSE). [START_REF] Yu | Experimental ultrasound characterization of red blood cell aggregation using the structure factor size estimator[END_REF] The SFSE is a second-order data reduction model based on the structure factor and adapted to a dense medium such as blood. This approach is based on the analysis of the backscattered power spectrum that contains information about the size, spatial organization, concentration and mechanical properties of scatterers (i.e. RBCs). The difficulty in using the SFSE in vivo is that the spectral content of backscattered echoes is also affected by attenuation caused by intervening tissue layers between the probe and the blood flow. More generally, US scatterer size estimation techniques for tissue characterization are facing similar challenges and several approaches to this problem have been developed. [START_REF] O'donnell | Relationship between collagen and ultra-sonic backscatter in myocardial tissue[END_REF][START_REF] Insana | Identifying acoustic scattering sources in normal renal parenchyma from the anisotropy in acoustic properties[END_REF][START_REF] Wear | Differentiation between acutely ischemic myocardium and zones of completed infarction in dogs on the basis of frequency-dependent backscatter[END_REF][START_REF] Van Der Steen | Correlation of histology and acoustic parameters of liver tissue on a microscopic scale[END_REF][START_REF] Wear | Measurements of ultrasonic backscatter coefficients in human liver and kidney in vivo[END_REF][START_REF] Hall | Ultrasonic measurement of glomerular diameters in normal adult humans[END_REF][START_REF] Lu | Ultrasound backscatter and attenuation in human liver with diffuse disease[END_REF][START_REF] Goss | Comprehensive compilation of empirical ultrasonic properties of mammalian tissues[END_REF][START_REF] He | Application of stochastic analysis to ultrasonic echoes -Estimation of attenuation and tissue heterogeneity from peaks of echo envelope[END_REF][START_REF] Yao | Backscatter coefficient measurements using a reference phantom to extract depth-dependent instrumentation factors[END_REF][START_REF] Oosterveld | Ultrasound attenuation and texture analysis of diffuse liver disease: methods and preliminary results[END_REF][START_REF] Roberjot | Absolute backscatter coefficient over a wide range of frequencies in a tissue-mimicking phantom containing two populations of scatterers[END_REF][START_REF] Bigelow | Estimation of total attenuation and scatterer size from backscatter ultrasound waveforms[END_REF][START_REF] Bigelow | Signal processing strategies that improve performance and understanding of the quantitative ultrasound SPECTRAL FIT algorithm[END_REF][START_REF] Bigelow | Evaluation of the Spectral Fit algorithm as functions of frequency range and ∆ka ef f[END_REF][START_REF] Franceschini | Simultaneous estimation of attenuation and structure parameters of aggregated red blood cells from backscatter measurements[END_REF] In vitro attenuation measurement methods are difficult to transfer in vivo since most of the clinical studies can be performed only in a single-transducer backscatter configuration. Indeed, in vitro backscatter coefficient measurements are generally compensated with an estimation of the attenuation using transmission mode [START_REF] O'donnell | Relationship between collagen and ultra-sonic backscatter in myocardial tissue[END_REF][START_REF] Insana | Identifying acoustic scattering sources in normal renal parenchyma from the anisotropy in acoustic properties[END_REF] or reflection mode with a reflector on the opposite side of the examined tissue, [START_REF] Wear | Differentiation between acutely ischemic myocardium and zones of completed infarction in dogs on the basis of frequency-dependent backscatter[END_REF][START_REF] Van Der Steen | Correlation of histology and acoustic parameters of liver tissue on a microscopic scale[END_REF] which is difficult to implement in clinical practice. Many researchers have then attempted to improve the in vivo backscatter power spectrum estimates by assuming a priori attenuation values for the different intervening tissue layers. [START_REF] Wear | Measurements of ultrasonic backscatter coefficients in human liver and kidney in vivo[END_REF][START_REF] Hall | Ultrasonic measurement of glomerular diameters in normal adult humans[END_REF][START_REF] Lu | Ultrasound backscatter and attenuation in human liver with diffuse disease[END_REF] Thicknesses of the intervening tissues are evaluated from the backscattered signals and typical attenuation values are assigned to each tissue, based on the results found in the relevant literature. Unfortunately, the tissue attenuation coefficients vary among patients (see for example the detailed review of the literature on tissue attenuation by Goss et al [START_REF] Goss | Comprehensive compilation of empirical ultrasonic properties of mammalian tissues[END_REF] ) and must be determined on a patient-specific basis. Several research groups have thus developped in vivo measurement techniques to evaluate the frequency-dependent attenuation for the compensation of the backscatter power spectrum. [START_REF] He | Application of stochastic analysis to ultrasonic echoes -Estimation of attenuation and tissue heterogeneity from peaks of echo envelope[END_REF][START_REF] Yao | Backscatter coefficient measurements using a reference phantom to extract depth-dependent instrumentation factors[END_REF][START_REF] Oosterveld | Ultrasound attenuation and texture analysis of diffuse liver disease: methods and preliminary results[END_REF][START_REF] Roberjot | Absolute backscatter coefficient over a wide range of frequencies in a tissue-mimicking phantom containing two populations of scatterers[END_REF] Recently, Bigelow and co-workers [START_REF] Bigelow | Estimation of total attenuation and scatterer size from backscatter ultrasound waveforms[END_REF][START_REF] Bigelow | Signal processing strategies that improve performance and understanding of the quantitative ultrasound SPECTRAL FIT algorithm[END_REF][START_REF] Bigelow | Evaluation of the Spectral Fit algorithm as functions of frequency range and ∆ka ef f[END_REF] have introduced a new algorithm that has the advantage to estimate simultaneously the effective radius of the tissue microstructure and the total attenuation. These two parameters were determined by using a single minimization method that fits the spectrum of the backscattered RF echoes from the region of interest (ROI) to an estimated spectrum by an appropriate model. In our previous work, this last strategy has been adapted for estimation of RBC scatterer sizes. [START_REF] Franceschini | Simultaneous estimation of attenuation and structure parameters of aggregated red blood cells from backscatter measurements[END_REF] Blood structural parameters and total attenuation were determined simultaneously by using an optimization method, termed the Structure Factor Size and Attenuation Estimator (SFSAE).

The goal of this paper was to further develop the SFSAE and assess its ability to evaluate three parameters (the packing factor, mean aggregate diameter and total attenuation) with in vitro experiments mimicking in vivo conditions. To insure that the global minimum of the optimization strategy is found, the algorithm was modified by employing an exhaustive search on the attenuation, combined with an analytical solution for the two blood structure parameters given for a fixed value of the attenuation, rather than a trust-region technique [START_REF] Coleman | A reective Newton method for minimizing a quadratic function subject to bounds on some of the variables[END_REF] used in our previous paper. [START_REF] Franceschini | Simultaneous estimation of attenuation and structure parameters of aggregated red blood cells from backscatter measurements[END_REF] Porcine RBCs were first sheared in a Couette flow system, and ultrasonic RF echoes were obtained using a 25 MHz center-frequency transducer. Four skin-mimicking phantoms with different attenuation coefficients were introduced between the transducer and the blood flow. Other experiments were conducted in a tubular flow allowing to be closer to the in vivo situation.

The theoretical framework describing the SFSAE development is given in section II.

Section III explains the two experimental setups. Section IV presents results and compares the new SFSAE with the SFSE with compensation for attenuation. The validation of the method is finally discussed in Section V.

II. STRUCTURE FACTOR SIZE AND ATTENUATION ESTIMATOR (SFSAE)

Ultrasonic scattering from blood is mainly caused by the RBCs. Indeed, blood can be mechanically described as a colloidal suspension of RBCs in plasma. RBCs constitute the vast majority (97%) of the cellular content of blood and occupy a large volume fraction (hematocrit) of 35-45% under normal conditions. These RBCs cannot be treated as independent scatterers since particle interactions (collision, attraction, deformation, flow dependent motions) are strong. The theoretical model of US backscattering by blood that we developped 7 is based on the particle approach, [START_REF] Mo | Theoretical models of ultrasonic scattering in blood[END_REF][START_REF] Twersky | Low-frequency scattering by correlated distributions of randomly oriented particles[END_REF] which consists of summing contributions from individual RBCs and modeling the RBC interaction by a particle pair-correlation function. Assuming that all the RBCs in the insonified blood are identical and using the Born approximation (weak scattering), the model predicts that the theoretical backscatter coefficient of blood is given by 23

BSC theor (k) = mσ b (k)S(k)A(k), ( 1
)
where k is the wavenumber, m is the number density of RBCs in blood, σ b is the backscattering cross section of a single RBC, S is the structure factor describing the spatial organization of RBCs, and A is the frequency-dependent attenuation function. The number density of RBCs m can be estimated by measuring the hematocrit H by microcentrifugation; m is then given by m = H/V s , where V s is the volume of a RBC (typically 87 µm 3 ). The backscattering cross-section σ b of a weak scatterer small compared to the wavelength (Rayleigh scatterer) can be determined analytically as follows:

σ b (k) = 1 4π 2 k 4 V 2 s γ 2 z , (2)
where γ z = (Z RBC -Z plasma )/Z plasma is the fractional variation of impedance between the RBC and its suspending medium (i.e. the plasma). The structure factor S is by definition the Fourier transform of the pair-correlation function [START_REF] Twersky | Low-frequency scattering by correlated distributions of randomly oriented particles[END_REF] g and can be approximated by its second-order Taylor expansion 7 in k as

S(k) = 1 + m (g(r) -1) e -2jkr dr ≈ W - 12 5 (kR) 2 . (3)
In this expression, g(r) represents the probability of finding two particles separated by a distance r. W is the low-frequency limit of the structure factor (S(k)| k→0 ) called the packing factor. [START_REF] Twersky | Low-frequency scattering by correlated distributions of randomly oriented particles[END_REF][START_REF] Shung | On the ultrasound scattering from blood as a function of hematocrit[END_REF] R is the radius of 3D RBC aggregates assumed to be isotropic. We introduce D = R/a as the isotropic diameter of an aggregate (expressed in number of RBCs) with a the radius of one RBC sphere-shaped model of volume V s . The attenuation function A is given by:

A(k) = e -4α 0 k 8.68 c 2π = e -4α 0 f /8.68 , ( 4
)
where c is the mean speed of sound in the intervening tissue layers, f is the frequency in MHz and α 0 is the attenuation coefficient (in dB/MHz) defined by: α 0 = i α i e i , where α i and e i are respectively the intervening tissue layer attenuations (in dB/cm/MHz) and thicknesses.

One can note in Eq. ( 4) the coefficient 8.68 that expresses unit conversion from dB to Neper:

α 0 [Neper/MHz]= α 0 [dB/MHz]/8.68. According to the above equation, we thus assume, as a first approximation, that the attenuation increases linearly with the frequency: α(f ) = α 0 f /8.68. Altogether, we obtain the following expression for the theoretical backscatter coefficient from blood:

BSC theor (k) = 1 4π 2 mk 4 V 2 s γ 2 z W - 12 5 (ka) 2 D 2 e -4α 0 k 8.68 c 2π . (5)
In particular, for a given value of the wavenumber k (equivalently, a given value of the frequency f ) and a given value of the attenuation coefficient α 0 , BSC theor (k) is a linear function of the variables W and D 2 .

The measured backscatter coefficient reported in this study was computed as

BSC meas (k) = BSC ref (k) P meas (k) P ref (k) . (6)
In Eq. ( 6), the mean backscattered power spectrum P meas was obtained by averaging the power spectra of 20 backscattered echoes from blood. The mean power spectrum P ref was obtained from a reference sample of non-aggregated RBCs at a low hematocrit of 6% (i.e.

Rayleigh scatterers). [START_REF] Wang | An approach for measuring ultrasonic backscattering from biological tissues with focused transducers[END_REF] In this case, 20 echoes were also averaged. The backscatter coefficient of this reference sample BSC ref was estimated by using the expression of the Perkus-Yevick packing factor for spheres W P Y s (that is a function of the hematocrit H) as follows: [START_REF] Twersky | Low-frequency scattering by correlated distributions of randomly oriented particles[END_REF][START_REF] Shung | On the ultrasound scattering from blood as a function of hematocrit[END_REF]

BSC ref (k) = mσ b (k)W P Y s = mσ b (k) (1 -H) 4 (1 + 2H) 2 . ( 7
)
This reference sample was used to compensate the backscattered power spectrum P meas for the electromechanical system response, and the depth-dependent diffraction and focusing effects caused by the US beam.

The packing factor W , aggregate diameter D and total attenuation along the propagation path α 0 were determined by matching the measured BSC meas given by Eq. ( 6)

with the theoretical BSC theor given by Eq. (5). For this purpose, we searched values of (W, D 2 , α 0 ) ∈ (0, ∞) × (0, ∞) × [0, 1], W and D being variables without dimension and α 0 expressed in dB/MHz, minimizing the cost function which synthesizes all of the wavenum-

bers k i (i = 1 • • • N) within the -20 dB bandwidth of P meas F (W, D 2 , α 0 ) = i ||BSC meas (k i ) -BSC theor (k i )|| 2 , = i ||BSC meas (k i ) - 1 4π 2 mk 4 i V 2 s γ 2 z W - 12 5 (k i a) 2 D 2 e -4α 0 k 8.68 c 2π || 2 . ( 8
)
The cost function had in the majority of cases reported in this study one minimum, as was observed by plotting the cost function surface F (W, D 2 , α 0 ) with varying values of α 0 . An example is given in Fig. 1. That is why a simple minimization routine lsqnonlin in Matlab (The MathWorks, Inc., Natick, MA), i.e. a trust-region method based on the interiorreflective Newton method, [START_REF] Coleman | A reective Newton method for minimizing a quadratic function subject to bounds on some of the variables[END_REF] was first employed in our previous paper. [START_REF] Franceschini | Simultaneous estimation of attenuation and structure parameters of aggregated red blood cells from backscatter measurements[END_REF] Nevertheless, on a possibility of the appearance of several minima, an exhaustive search on the value of α 0 was employed in this paper in order to insure that the global minimum is found. If the value of α 0 is fixed, a quadratric function of the two variables W and D 2 is obtained, as can be seen from Eq. ( 8), and by calculating its critical points, a system of two linear equations of two unknowns can be easily solved. One can show using the Cauchy-Schwartz' inequality that the determinant of this system never vanishes (unless all frequencies are equal) and thus, that the solution is unique. If the unique solution of this system denoted (W * (α 0 ), D 2 * (α 0 )) is such that W * (α 0 ) ≤ 0 or D 2 * (α 0 ) ≤ 0, then the cost function F (W, D 2 , α 0 ) has no global minimum on (0, ∞) × (0, ∞) (with the value of α 0 fixed). Also, this case means that the value of α 0 has to be rejected, since it is meaningless. Otherwise, the global minimum of F (W, D 2 , α 0 ) on (0, ∞) × (0, ∞) occurs at (W * (α 0 ), D 2 * (α 0 )). In practice, there is a maximal value α * of α 0 between 0 and 1 dB/MHz, for which W * (α 0 ) ≥ 0 and D 2 * (α 0 ) ≥ 0. Thus, the global minimum of

F (W, D 2 , α 0 ) on the domain (0, ∞) × (0, ∞) × [0, α * ] is the global minimum of the function F (W * (α 0 ), D 2 * (α 0 ), α 0 ) on the interval [0, α * ].
The optimal value of α 0 can thus be obtained upon sweeping the interval [0, α * ]. In our tests, we started the exhaustive search with a step of 10 -5 dB/MHz. Then, the step was iteratively decreased by a factor of 10 -1 dB/MHz, while the search is performed on the interval of length twice the preceeding step around the best value obtained so far. The iterative (multi-resolution) exhaustive search was stopped after a step of 10 -20 dB/MHz. At the end of the SFSAE algorithm, a simple test allowed to verify the validity of the solution. If the solution (W, D 2 , α 0 ) of the optimization problem was such that W or D 2 was on the inferior boundary of the domain (i.e. W or D 2 are equal to zero), the solution was rejected since such values of W or D 2 are unrealistic.

This last point will be discussed later in section V.D.

III. METHODS

A. Blood samples preparation

Blood from two different pigs were used for the two experiments in a Couette device and in a tube. This fresh porcine whole blood was obtained from a local slaughter house and anticoagulated with 3 g/L of ethylene diamine tetra acetic acid (EDTA). Then the whole blood was centrifuged and the plasma and buffy coat were removed. Two blood samples were then prepared for each experiment: (i) a H6 reference sample, which was a 6% hematocrit non-aggregating RBCs resuspended in physiological saline solution; and

(ii) a 40% hematocrit T40 test sample, which consisted of RBCs resuspended in plasma to promote aggregation.

B. In vitro experiments

In vitro experiments in a Couette flow system (Couette device)

US measurements were first performed in a Couette device to produce a linear blood velocity gradient at a given shear rate (see Fig. 1 in Ref. 29). The system consists of a rotating inner cylinder with a diameter of 160 mm surrounded by a fixed concentric cylinder of diameter 164 mm. A 60 mL blood sample was sheared in the 2 mm annular space between both coaxial cylinders. An US scanner (Vevo 660, Visualsonics, Toronto, Canada) equipped with the RMV 710 probe was used in B-mode. The oscillating single-element focused circu-lar transducer had a center frequency of 25 MHz, a diameter of 7.1 mm and a focal depth of 15 mm. We acquired RF data from this scanner at a sampling frequency of 250 MHz with 8 bits resolution (Gagescope, model 8500CS, Montreal, Canada). The probe was mounted in the side wall of the fixed outer cylinder and was positioned to have its focal zone at the center of the gap between both cylinders. To ensure ultrasonic coupling, the hole within the outer stationary cylinder (containing the probe) was filled with a liquid agar gel based mixture. When solidified, this gel was cut to match the curvature of the cylinder to avoid any flow disturbance. The gel was a mixture of distilled water, 3% (w/w) agar powder (A9799, Sigma Chemical, Saint-Louis, MO), 10% (w/w) glycerol and a specific concentration of 50 µm cellulose scattering particles (S5504 Sigmacell, Sigma Chemical, Saint-Louis, MO) that determined the attenuation coefficient. Five experiments were performed with five mixtures having SigmaCell (SC) concentrations varying from 0% to 1% (w/w). The 0% concentration constituted the non-attenuating gel and the four other mixtures mimicked skin attenuations.

All US measurements were made at room temperature. Prior to each measurement, the T40 blood was sheared at 200 s -1 during 30 s to disrupt RBC aggregates. The shear rate was then reduced to residual values of 5, 10, 20, 30 and 50 s -1 for 90 s until an equilibrium in the state of aggregation was reached. For each shear rate, 20 B-mode images were constructed from acquired RF echoes each 4 s for a total period of analysis of 80 s. Each image contained 384 vertical lines. For 180 vertical lines at the center of the B-mode images, echoes were selected with a rectangular window of axial length 0.4 mm at 20 depths every 0.031 mm (i.e. with 92% overlap between windows). For each depth, the power spectra of the backscattered RF echoes were averaged over 20 acquisitions (corresponding to the 20 acquired B-mode images) to provide P meas . This protocol was repeated five times with the same blood and with each of the five agar-based phantoms.

Then, the T40 blood was removed and the H6 sample was introduced in the Couette device. The H6 sample was sheared at 50 s -1 and coupled with the 0% SC concentration agar gel. Echoes were windowed as for the H40 sample at the same depths and their power spectra were averaged over 20 acquisitions to obtain P ref . This reference power spectrum allowed to normalize the average power spectrum P meas (as described in Eq. ( 6), section II).

In vitro experiments in a tube

In order to be closer to in vivo conditions, US measurements were also performed in a tubular flow device. The experimental test section was an horizontal tube made of PolyVinyl Alcohol (PVA) cryogel. This tube had an internal diameter of 4.9 mm and a length of 10 cm, and was immersed in a tank filled with degassed water at room temperature. The US measurements were made at a position 7 cm from the tube entrance with the Vevo 660 US scanner. The transducer focal point at 15 mm was positioned at the middle of the tube, imaged in the longitudinal plane. The T40 blood sample was circulated in the PVA tube using a double syringe pump (Harvard PHD 2000) at a constant flow rate from the outflow syringe, to the tube and the second inflow syringe. In order to ensure that the RBCs are disaggregated at the tube entrance, the T40 sample blood passed through a small recipient containing a magnetic stirrer just before entering the PVA tube, as indicated in Fig. 2(a).

Similarly to the Couette experiments (section III.B.1), a layer of gel was placed between the probe and the tubular flow. Five experiments were successively performed on the same blood with five mixtures having SC concentrations: 0, 1, 1.5, 2 and 2.5% (w/w).

The flow rate was chosen equal to 5 ml/min to promote RBC aggregation and when 30 ml of blood had circulated in the tube, 20 B-mode images were constructed for 80 s.

The data was processed as described for the in vitro experiment in the Couette device, except that echoes were selected with a rectangular window of length 0.4 mm at 65 depths every 0.031 mm (again with 92% overlaps). A reference measurement was done by using the H6 sample circulating in the tube at a flow rate of 5 ml/min. Echoes were windowed as for the H40 sample at the same 65 depths and their power spectra were averaged over 20 acquisitions to obtain P ref . One can note here that P ref allow to compensate P meas not only for the electromechanical system response, and the depth-dependent diffraction and focusing effects caused by the US beam, but also for the US response of the PVA cryogel tube.

Attenuation measurements for comparison with the SFSAE attenuation estimates

The attenuation coefficients of the reference (0% SC) and of the skin-mimicking phantoms were determined by using a standard substitution method. The Vevo 660 US scanner equipped with the same RMV 710 25 MHz transducer was used in M-mode and in transmission/reception with a reflector on the opposite side of the phantom for reflection measurements. Reflected signals were recorded both with and without the agar gel sample in the acoustic path. The attenuation coefficient was then estimated using a log spectral difference technique. [START_REF] Kuc | Estimating the acoustic attenuation coefficient slope for liver from reflected ultrasound signals[END_REF] For a given concentration of SC, measurements were obtained from two different sample thicknesses, and for each, six regions were scanned for averaging purpose. I.

As it can be observed in this table, attenuation coefficients of skin-mimicking phantoms were in the same range as the human dermis (which is 0.21 dB/MHz at 14 -50 MHz considering a 1 mm dermis thickness [START_REF] Raju | High-frequency ultrasonic attenuation and backscatter coefficients of in vivo normal human dermis and subcutaneous fat[END_REF] ).

For the Couette device configuration, blood attenuation was also measured at different shear rates in the reflection mode. The gel had a 0% SC concentration, the probe was used in M-mode and the rotating inner cylinder was used as the reflector. For each shear rate, acquisitions of 20 RF lines were performed both with blood and with water in the Couette device. The water acquisition was used for normalization. For each acquisition, blood attenuation was estimated using the log spectral difference technique. These values were then averaged to provide α blood . Values obtained were 0.053 ± 0.011, 0.036 ± 0.008,

BSC meas (k) = BSC ref (k) P meas (k) P ref (k) e -4 8.68 (α blood e blood +α SC e SC )k c 2π , (9)
and the parameters W ref and D ref were deduced by fitting the measured backscatter coefficient to the theoretical backscatter coefficient using the classical SFSE:

7 BSC theor (k) = 1 4π 2 mk 4 V 2 s γ 2 z W ref - 12 5 (ka) 2 D 2 ref . (10)
The parameters W ref and D ref were assumed to be true values of packing factors and aggregate diameters at all shear rates, and will be compared in the next section with packing factors and diameters estimated by the SFSAE when skin-mimicking phantoms were used. The black pixels in the ROI correspond to rejected solutions of the optimization method (when the estimated packing factor W or diameter D 2 was found equal to zero, which is unrealistic). A clear distinction between images of the estimated total attenuation with the four skin-mimicking phantoms is apparent, which was expected, whereas images of the estimated parameters W and D are quite similar, which was also wished.

IV. RESULTS

A. In vitro experiments in the Couette device

For each residual shear rate, quantitative images for the three parameters W , D and α 0 were constructed. The average estimates are summarized in Figure 6. The lower and upper error bars for relative errors correspond to:

ǫ lower = (X -σ X ) -(X ref -σ X ref ) X ref -σ X ref , ǫ upper = (X + σ X ) -(X ref + σ X ref ) X + σ X ref , (11)
where X represents one of the estimated parameters W , D or α 0 . For all shear rates and all skin-mimicking phantoms, the SFSAE gave quantitatively satisfactory estimates of W and D with relative absolute errors below 25%, except for the shear rate of 5 s -1 and the 0.25% SC skin-mimicking phantom.

The use of the SFSAE when there is little attenuation (i.e. the 0% SC phantom) was also investigated. Figure 7 presents the averaged parameters W , D and α 0 obtained from the SFSAE with the 0% SC phantom. In this experiment, the total attenuation came mainly from the blood (0.015≤ α blood ≤0.053 dB/MHz) and a little part from the SC phantom (0.007 dB/MHz). Also represented in Fig. 7 are the SFSAE results with the 0.25% SC phantom in order to compare the SFSAE performance in the presence of higher attenuation. When there is little attenuation, estimates of W were less accurate for shear rates of 5, 10 and 20 s -1 (in comparison with W obtained with the four other SC phantoms) with relative errors between 25 and 42%. Estimates of α 0 were between 0.041 and 0.133 dB/MHZ, so the total attenuation were overestimated giving the largest relative errors between 124 ad 211%.

Finally, to support the discussion reported later, the packing factor W comp and the In order to know the shear rate profile in the tube, a speckle tracking method [START_REF] Shehada | Ultrasound methods for investigating the nonnewtonian characteristics of whole blood[END_REF] was used to obtain the displacement fields of RBCs as shown in Fig. 2(b). The displacement of the speckle pattern between each frame is then related to the velocity through the time elapsed between the images. The mean velocity profile across the tube was fitted to the following simple power law model:

v(r) = v max (1 -(r/R) n ) , (12)
where v(r) is the mean velocity at radius r, R the radius of the tube, v max the maximum velocity, and n the power-law exponent (n = 2 for parabolic flow). As expected, the velocity profile was slightly blunted due to RBC aggregation with n = 2.99 [see Fig. 2(b)]. The shear rate profile, γ(r), was deducted from this velocity profile by computing the derivative of v(r):

γ(r) = - ∂v(r) ∂r = nv max r n-1 R n . ( 13
)
Five shear rates were selected on the shear rate profile (i.e. 0.1, 0.3, 1, 1.5 and 2 s -1 ) corresponding to specific depths [see Fig. 3) and of α blood e blood , with e blood varying for each shear rate. The blood attenuation α blood was arbitrarily chosen to be equal to 0.028 dB/mm/MHz. This point will be discussed later in section V.A. Figure 10 summarizes these results. The SFSAE gave estimates of W , D and α 0 with relative errors below 25% for all skin-mimicking phantoms at shear rates between 0.3 and 2 s -1 . Worse estimates were obtained for the smallest shear rate of 0.1 s -1 :

for 1% and 1.5 % SC concentrations, relative errors for W were 61% and 32% respectively, those for α 0 were 56% and 47% respectively, whereas those for D remained below 20%.

V. DISCUSSION

A. The difficulty to measure the blood attenuation in a tube flow device

The following discussion intends to explain why blood attenuation values in function of the shear rate cannot be obtained directly by measurements in a tube by a standard substitution method. The ideal protocol would be to realize blood attenuation measurements on a Couette apparatus (as performed in section III.B.3) for the different shear rates present in the tube. In our experiments, the tube was not long enough (kinetic time) to obtain the same aggregate sizes as in the Couette device, that is why we chosen a mean blood attenuation equal to 0.028 dB/mm/MHz corresponding to the average of blood attenuations estimated with the Couette device for the different shear rates (see section III.B.3).

B. Limitations of the SFSAE with respect to kR and attenuation

For both Couette and tubular flow devices, the SFSAE gave good estimates of W , D and α 0 with relative errors below 25% for all skin-mimicking phantoms and for all shear rates, except for the smallest shear rates and the smallest attenuations (0.115 dB/MHz for the Couette and 0.142 dB/MHz for the tube): relative errors for W were around 50% (Couette) and 61 % (tube), for α 0 around 48% (Couette) and 56% (tube), for D below 25% as indicated in figures 6 and 10. In the tube experiment, one can also notice that relative errors for α 0

were always worse at the smallest shear rate (0.1 s -1 ) for all skin-mimicking phantoms. For the peculiar case when there is little attenuation (i.e. ≤ 0.06 dB/MHz), the SFSAE did not give accurate results (absolute relative errors reaching 42% for W and 211% for α 0 ).

For the Couette device, the correlation coefficients given in Tables III, IV and V reveal that the SFSAE produced quite good fits to data for all skin-mimicking phantoms and all shear rates, i.e. 0.74 ≤ r 2 ≤ 0.91. Nevertheless, for both SFSE and SFSAE models, the smallest r 2 values occurred at the lowest shear rate of 5 s -1 . It is illustrated by fits of SFSE and SFSAE models in Fig. 4 that are worse at 5 s -1 (in comparison with fits at 10 and 50 s -1 ), especially for the largest attenuation.

Considering the correlation coefficients and the accuracy of the estimates, both SFSE and SFSAE seem to reach their limit of applicability for large aggregate sizes: for the Couette It is interesting to note that the limitations of the SFSAE can be used to interpret the attenuation quantitative images obtained in the tubular flow device (Fig. 9). Indeed, these images are less homogeneous compared to those obtained in the Couette device since the standard deviations for attenuation were between 0.052 and 0.082 dB/MHz for the tube and between 0.033 and 0.063 dB/MHz for the Couette. It is clearly linked with the presence of shear rates < 0.3 s -1 ) in the tube experiments that result in large aggregate sizes outside the validity domain of the SFSAE.

C. Comparison of the SFSAE and SFSE with compensation for attenuation

For the Couette experiments, relative errors for W and D were generally below 25%

(except for one value) with the SFSAE (Fig. 6) and with the SFSE with attenuationcompensation (Fig. 8). For W at 5 s -1 and a 0.25% SC, the SFSAE was not in its validity domain. In the SFSAE validity domain, the accuracy of the estimates obtained with the SFSAE was thus as satisfactory as those obtained with the SFSE with attenuationcompensation. The SFSAE has the major advantage to be easily applicable in vivo contrary to the SFSE attenuation-compensation method, needing the attenuation and thickness of the tissue intervening layers to be known.

D. Rejected solutions

In figures 5 and 9, one can notice the rejected solutions represented in black pixels.

These solutions were rejected because their estimated diameters were equal to 0 (whereas the estimated packing factors never vanish). One might think that these rejected solutions come from cost functions having several local minima. Several cases of rejected solutions were studied and their corresponding cost functions had always a unique global minimum (data not shown).

To better understand what happened in these special cases, figure 11 for the rejected solutions, that both W and α 0 were overestimated. This phenomenon can be explained by the difficulty to evaluate simultaneously three parameters that have the same effect on the backscatter coefficient as explained below. Figure 11(b) illustrates the respective effect of varying W , D and α 0 on the backscatter coefficient. We arbitrarily selected a shear rate of 50 s -1 (i.e. a quasi-disaggregated case) and no SC attenuation. An increase in W has the effect of increasing the amplitude of the backscatter coefficient at all frequencies; whereas increasing D has an effect on the frequency dependence. But more interesting is to observe that an increase in α 0 has the effect of decreasing the amplitude and also of modifying the frequency dependence of the backscatter coefficient. It is thus difficult to estimate simultaneously these three parameters, because a modification in α 0 plays the same role (i.e. effects on the amplitude and the frequency dependence) that modifications in W (i.e. amplitude) and D (i.e. frequency dependence). The typical example given in Fig. 11(a) and parameter values presented in Fig. 12 can now be better understood. When the optimization method gives an unrealistic estimate of D equal to 0, the frequency dependence of the backscatter coefficient is only given by α 0 , which is overestimated. But since increasing α 0 has also the effect of decreasing the amplitude of the backscatter coefficient, the overestimation of α 0 goes with the overestimation of W .

Figure 13 gives the percentage of rejected solutions in the ROIs (i.e. 20 depths and 180 RF lines for the Couette as shown in Fig. 5, and 3 depths and 180 RF lines for the tube) at each shear rate for both Couette and tubular flow devices. For both devices, it can be clearly observed that percentages of rejected solutions are highest for experiments with the smallest attenuation (0.25% SC for the Couette and 1% SC for the tube) and with the highest shear rate, i.e. with quasi-disaggregated RBCs (50 s -1 for the Couette and 2 s -1 for the tube). The rejected solutions were thus more important when the frequency dependence was nearly Rayleigh. In our previous study, [START_REF] Franceschini | Simultaneous estimation of attenuation and structure parameters of aggregated red blood cells from backscatter measurements[END_REF] we did not reject solution, that is why bad estimates were obtained for quasi-disaggregated RBCs. The rejection of some solutions was vital for having accurate results in the cases of quasi-disaggregated RBCs and of small total attenuation.

E. On the use of the SFSAE in vivo

The accuracy of the SFSAE was quantitatively demonstrated in a validity domain. One might question the use of this method in vivo. Although the SFSAE gave estimates with large errors for kR > 2.08 and α 0 ≤ 0.06 dB/MHz, the estimated parameters presented in

VI. CONCLUSION

Aggregating porcine RBCs were examined using US via in vitro experiments in Couette and tubular flow devices. Estimates of blood structural parameters and total attenuation were made from the frequency dependence of the US backscatter using the SFSAE model.

This study revealed that the SFSAE provided accurate quantitative estimates of blood microstructure parameters W and D for kR < 2.08 and for total attenuations between 0.115 and 0.411 dB/MHz. In this validity domain, the results obtained with the SFSAE was quantitatively as satisfactory as those obtained with the SFSE with attenuation compensation (i.e., when prior information on the attenuation is available). Outside this validity domain, the SFSAE was able to give the aggregation state tendency.

The SFSAE has been shown to be able of estimating blood backscattering properties in the presence of tissue intervening layers. This method is easily applicable in vivo because of the simultaneous estimation of the blood structural properties and total attenuation, contrary to the SFSE attenuation-compensation method, needing the attenuation and thickness of the tissue intervening layers to be known. Future works should focus on in vivo and in situ assessment of the pathophysiological impact of abnormal RBC aggregation on the cardiovascular system.

  In our experimental devices, thicknesses of skin-mimicking phantoms e SC were fixed to 1.3 cm in the case of the Couette device and 0.45 cm for the tubular flow experiments. Values of the average attenuations α SC expressed in dB/cm/MHz and of the attenuation coefficients α SC e SC expressed in dB/MHz for the Couette and tube experiments are reported in Table

4 .

 4 Reference measurements for blood structural parameters with the 0% SC concentration phantom for in vitro experiments For both in vitro devices, experiments with the 0% SC phantom were realized in order to have reference results on packing factors W ref and aggregate diameters D ref . For these reference measurements, the measured backscatter coefficient was compensated for predetermined values of blood and 0% SC phantom attenuations and thus computed as follows:

Figure 3

 3 Figure 3 shows the typical BSC meas as a function of frequency for different residual shear rates in the case of 0% SC (i.e. reference measurements). Also represented are corresponding fitted curves obtained with the SFSE after compensation for predetermined values of blood attenuation. The parameters W ref and D ref were estimated over 20 depths and 180 RF lines of the B-mode image (i.e. 3600 estimations) in a chosen ROI. Their mean values W ref , D ref as well as their standard deviations σ W ref , σ D ref are reported in TableII. It can be noticed

Figure 5

 5 Figure 5 shows quantitative images superimposed on the gray-scale B-mode images of the blood sheared at 10 s -1 in the Couette device. The color of each pixel was assigned based on the value of the parameters estimated by the SFSE with the 0% SC phantom and

Figure 9

 9 Figure9shows quantitative images superimposed on the gray-scale B-mode images of tubular blood flow for each skin-mimicking phantom. As observed in the Couette experiment, a clear distinction between images of the estimated total attenuation is apparent, whereas images of the estimated parameters W and D are quite similar.

  2(b)] and thus corresponding to specific blood thicknesses (i.e. 2.7, 2.9, 3.4, 3.6 and 3.8 mm). For each shear rate, values of W , D and α 0 were simultaneously estimated by the SFSAE and averaged over 3 depths (one specific depth and their two adjacent depths i.e. ±0.031 mm) and 180 lines of the B-mode image. These average values of W and D obtained with the SFSAE were compared with average values of W ref and D ref evaluated by the SFSE with attenuation-compensation. The reference total attenuation α ref was the sum of α SC e SC estimated in the reflection mode (see section III.B.

  experiments, typically D ref = 10.11 in Table II (i.e. kR = 2.88 with f = 25 MHz ) and for the tube experiments, typically D ref = 7.29 in Fig.10 (i.e. kR = 2.08). To conclude, the SFSAE performed well for kR < 2.08 and for total attenuations between 0.115 and 0.411 dB/MHz. In the following, these bounds will define the SFSAE validity domain, i.e. the domain where the SFSAE gives accurate estimates of W , D and α 0 .

  (a) represents two backscatter coefficients for blood sheared at 20 s -1 in the Couette flow device and measured with the 0.25% SC concentration phantom. Although both experimental backscatter coefficient were quite similar, the corresponding fitted models with the SFSAE gave two very different estimates of W , D and α 0 . One estimation corresponds to a kept solution and the other to a rejected solution with an estimate of D equal to 0. In Fig. 12 are summarized the mean values of W , D and α 0 for the kept and rejected solutions estimated with the SFSAE for all shear rates and for the 0.25% SC concentration phantom. It can be observed,

figures 6 and 10

 10 figures 6 and 10 show that the SFSAE gave qualitatively satisfactory estimates for all SC phantoms at all shear rates, since the estimates of W and D versus shear rates had the same behaviors as W ref and D ref . It means that the validity of estimates is possible for in vivo experiments, since the SFSAE is able to predict the aggregation state and attenuation tendencies.

  obtained with the SFSE (0% SC), and values of the packing factor W , diameter D and attenuation α 0 obtained with the SFSAE (0.25, 0.5, 0.75 and 1% SC) at the shear rate 5 s -1 in the Couette flow device. The parameter ǫ indicates the relative error and r 2 the correlation coefficient of the fitted SFSAE model on experimental data BSC meas . Table IV. Reference values of the packing factor W ref and diameter D ref obtained with the SFSE (0% SC), and values of the packing factor W , diameter D and attenuation α 0 obtained with the SFSAE (0.25, 0.5, 0.75 and 1% SC) at the shear rate 10 s -1 in the Couette flow device. The parameter ǫ indicates the relative error and r 2 the correlation coefficient of the fitted SFSAE model on experimental data BSC meas . Table V. Reference values of the packing factor W ref and diameter D ref obtained with the SFSE (0% SC), and values of the packing factor W , diameter D and attenuation α 0 obtained with the SFSAE (0.25, 0.5, 0.75 and 1% SC) at the shear rate 50 s -1 in the Couette flow device. The parameter ǫ indicates the relative error and r 2 the correlation coefficient of the fitted SFSAE model on experimental data BSC meas .

Figure captions Figure 1 .

 captions1 Figure captions

Figure 2 .

 2 Figure 2. (Color online) (a) Diagram of the experimental apparatus used in the tubular flow experiments. (b) Echographic image of the T40 blood in the tube (obtained with the US scanner Visualsonics) and estimates of particle displacement fields by B-mode speckle tracking and corresponding mean velocity and shear rate as a function of depths in the tube.

Figure 3 .

 3 Figure 3. (Color online) Backscatter coefficients for blood sheared at different residual shear rates and measured with the 0% SC concentration phantom, and corresponding fitting with the classical SFSE with compensation for blood attenuation (in dashed lines).

Figure 4 .

 4 Figure 4. (Color online) Measured backscatter coefficients for blood sheared at 5, 10 and 50 s -1 and with each of the five phantoms. The corresponding fitted models (in dashed lines) are the SFSE for the 0% SC phantom with compensation for blood attenuation (black squares), and the SFSAE for the four skin-mimicking phantoms (0.25, 0.5, 0.75 and 1% SC).

Figure 5 .

 5 Figure 5. (Color online) Quantitative images of blood sheared at 10 s -1 in the Couette device superimposed on the gray-scale B-mode images. Parameters were estimated by the classical SFSE with compensation for blood attenuation for the 0% SC concentration (top panel) and by the SFSAE for the four skin-mimicking phantoms.

Figure 6 .

 6 Figure 6. (Color online) (a) Values of W , D and α 0 (in dB/MHz) for different residual

Figure 7 .

 7 Figure 7. (Color online) (a) Values of W , D and α 0 (in dB/MHz) for different residual shear rates estimated by the SFSAE for the 0% and 0.25% SC concentrations. Also represented are values of W ref and D ref estimated by the classical SFSE with compensation for blood attenuation for the 0% SC concentration and values of α ref in dashed lines. (b) Corresponding relative errors of W , D and α 0 .

Figure 8 .

 8 Figure 8. (Color online) (a) Values of W comp and D comp for different residual shear rates estimated by the classical SFSE with compensation for attenuation by taking predetermined values measured in reflection mode for the four skin-mimicking phantoms (mean ± standard deviation). (b) Corresponding relative errors of W comp and D comp .

Figure 9 .

 9 Figure 9. (Color online) Quantitative images of blood sheared in a tube superimposed on the gray-scale B-mode images. Parameters were estimated by the classical SFSE with compensation for blood attenuation for the 0% SC concentration (top panel) and by the SFSAE for the four skin-mimicking phantoms.

Figure 10 .

 10 Figure 10. (Color online) (a) Values of W , D and α 0 (in dB/MHz) for different shear rates estimated by the SFSAE for the four skin-mimicking phantoms in the tube experiments (mean ± standard deviation). Also represented are values of W ref and D ref estimated by the classical SFSE with compensation for blood attenuation for the 0% SC concentration and values of α ref in dashed lines. (b) Corresponding relative errors of W , D and α 0 .

Figure 11 .

 11 Figure 11. (Color online) (a) Two backscatter coefficients for blood sheared at 20

Figure 12 .

 12 Figure 12. (Color online) (a) Values of W , D and α 0 (in dB/MHz) for the kept and rejected solutions of the SFSAE for different residual shear rates and for the 0.25% SC concentration phantom in the Couette experiment (mean ± standard deviation). (b) Corresponding relative errors of W , D and α 0 .

Figure 13 .

 13 Figure 13. (Color online) Percentage of rejected solutions in the ROIs: 20 depths and 180 RF lines for the Couette and 3 depths and 180 RF lines for the tube.

  FIG. 1.

Frequency

  FIG. 4.

  FIG. 5. 39

  FIG. 6.

  FIG. 7.

  FIG. 8.

  FIG. 9. 43

  FIG. 10.

1 )Fitted

 1 FIG. 11.

Table I .

 I Values of the average attenuations α SC of skin-mimicking phantoms expressed in dB/cm/MHz and corresponding attenuation coefficients α SC e SC expressed in dB/MHz for the Couette and tube experiments. Table II. Reference values of the packing factor W ref and diameter D ref obtained with the SFSE at different residual shear rates. The parameter r 2 represents the correlation coefficient of the fitted SFSE model on experimental data BSC meas .

Table III .

 III Reference values of the packing factor W ref and diameter D ref

TABLE I .

 I

							TABLE II. TABLE III. TABLE V.
	Shear rate SC (%) SC (%) SC (%)	0 0 0	W ref	Attenuation coefficient D ref 0.25 0.5 0.25 0.5 0.25 0.5	Attenuation coefficient r 2 0.75 1 0.75 1 0.75 1
	Sigmacell (SC) s -1 W ref W ref W ref	Attenuation 24.56 ± 2.82 9.14 ± 1.89 0.44 ± 0.10	for the Couette flow device for the tube flow device ------------
	concentration 5 W W W	α SC 24.56 ± 2.82 -36.97 ± 12.40 23.33 ± 8.96 26.83 ± 8.65 23.01 ± 6.83 α SC e SC (e SC =1.3 cm) α SC e SC (e SC =0.45 cm) 10.11 ± 0.72 0.67 ± 0.02 -10.14 ± 3.03 9.35 ± 2.73 9.08 ± 1.93 10.86 ± 3.88 -0.46 ± 0.19 0.53 ± 0.21 0.38 ± 0.15 0.35 ± 0.11
	(%) 10 ǫ W (%) ǫ W (%) ǫ W (%)	(dB/cm/MHz) 9.14 ± 1.89 -50.53 -10.94 -4.54	(dB/MHz) 4.59 ± 0.78 -0.65 2.29 20.45	9.24 -0.65 -13.64	(dB/MHz) 0.95 ± 0.02 -6.31 18.81 -20.45
	20 D ref D ref D	0	0.0054 ± 0.0015 3.90 ± 0.79 10.11 ± 0.72 4.59 ± 0.78 0.82 ± 0.23	---	0.0070 ± 0.0019 2.68 ± 0.54 ---	---	0.0024 ± 0.0006 0.93 ± 0.03 ---
	D D D	0.25 30	0.088 ± 0.018 1.39 ± 0.34 -10.87 ± 1.74 9.05 ± 1.61 11.11 ± 1.68 11.08 ± 1.68 0.115 ± 0.024 -1.35 ± 0.38 0.95 ± 0.02 -5.25 ± 1.01 4.83 ± 4.84 ± 0.55 5.07 ± 1.26 -0.89 ± 0.24 0.98 ± 0.28 0.90 ± 0.21 1.02 ± 0.19
	0.5 50 ǫ D (%) ǫ D (%) ǫ D (%)	0.168 ± 0.023 0.44 ± 0.040 -7.52 -14.38 -8.54	0.219 ± 0.030 0.82 ± 0.23 -10.48 5.23 19.51	9.89 5.45 9.76	-0.95 ± 0.03 9.59 10.45 24.39
	0.75 α ref (dB/MHz) 0.060 ± 0.018 0.168 ± 0.035 0.272 ± 0.041 0.373 ± 0.046 0.464 ± 0.051 0.246 ± 0.027 0.320 ± 0.035 -α ref (dB/MHz) 0.043 ± 0.010 0.151 ± 0.032 0.255 ± 0.038 0.356 ± 0.043 0.447 ± 0.048 α ref (dB/MHz) 0.022 ± 0.005 0.130 ± 0.027 0.234 ± 0.033 0.335 ± 0.038 0.426 ± 0.043
	1 α 0 (dB/MHz) α 0 (dB/MHz) α 0 (dB/MHz)	0.316 ± 0.031 -0.246 ± 0.045 0.314 ± 0.046 0.409 ± 0.048 0.445 ± 0.051 0.411 ± 0.040 0.142 ± 0.014 -0.172 ± 0.061 0.283 ± 0.053 0.367 ± 0.033 0.410 ± 0.057 -0.148 ± 0.059 0.287 ± 0.060 0.370 ± 0.061 0.409 ± 0.063
	1.5 ǫ α 0 (%) ǫ α 0 (%) ǫ α 0 (%)	0.475 ± 0.053 ---	46.43 13.91 13.85	-	15.44 10.98 22.65	9.65 3.09 10.45	0.214 ± 0.024 -4.09 -8.28 -3.99
	r 2 r 2 r 2		2	0.633 ± 0.051 0.67 ± 0.02 0.81 ± 0.06 0.79 ± 0.05 0.79 ± 0.07 0.74 ± 0.05 -0.285 ± 0.023 0.95 ± 0.02 0.86 ± 0.06 0.84 ± 0.08 0.86 ± 0.08 0.81 ± 0.06 0.95 ± 0.03 0.91 ± 0.04 0.90 ± 0.06 0.86 ± 0.05 0.86 ± 0.06
		2.5	0.768 ± 0.060			-	0.346 ± 0.027

Shear rate 50 s -1 Shear rate 10 s -1 Shear rate 5 s -1

	10 -1	10 -1
		Attenuation	Attenuation
		in dB/MHz	in dB/MHz
	10 -2	)	0.060	0.043
	10 -3	.sr -1 BSC (cm -1	0.168 0.272 0.373 0.464	0.151 Shear rate 10 s -1 0.255 Shear rate 5 s -1 0.356 0.447	0.022 Attenuation in dB/MHz
				Shear rate 20 s -1	0.130
	10 -4			Shear rate 30 s -1	0.234 0.335
				Shear rate 50 s -1	0.426
	10 -5
	6 8 10	20 30 40	Frequency (MHz) 6 8 10 20 30 40	6 8 10	20 30 40
			FIG. 3.

Acknowledgments

This work was supported by the Canadian Institutes of Health Research (grants ♯MOP-84358 and CMI-72323), by the Heart and Stroke Foundation of Canada (grant ♯PG-05-0313), and by the National Institutes of Health of USA (grant ♯RO1HL078655).