Giovanni Pighizzini
email: pighizzini@di.unimi.it

Luca Prigioniero
email: prigioniero@di.unimi.it

Pushdown Automata and Constant Height: Decidability and Bounds

It cannot be decided whether a pushdown automaton accepts using constant pushdown height, with respect to the input length, or not. Furthermore, in the case of acceptance in constant height, the height cannot be bounded by any recursive function in the size of the description of the machine. In contrast, in the restricted case of pushdown automata over a one-letter input alphabet, i.e., unary pushdown automata, the above property becomes decidable. Moreover, if the height is bounded by a constant in the input length, then it is at most exponential with respect to the size of the description of the pushdown automaton. This bound cannot be reduced. Finally, if a unary pushdown automaton uses nonconstant height to accept, then the height should grow at least as the logarithm of the input length. This bound is optimal.

Introduction

The investigation of computational devices working with a limited amount of resources is a classical topic in automata theory. It is well known that by limiting the memory size of a device by some constant, the computational power of the resulting model cannot exceed that of finite automata. For instance, if we consider pushdown automata in which the maximum height of the pushdown is limited by some constant, the resulting devices, called constant-height pushdown automata, can recognize only regular languages. Despite their limited computational power, constant-height pushdown automata are interesting since they allow more succinct representations of regular languages than finite automata [START_REF] Geffert | More concise representation of regular languages by automata and regular expressions[END_REF]. A natural generative counterpart of these devices are non-selfembedding context-free grammars, roughly context-free grammars without "true" recursion [START_REF] Chomsky | A note on phrase structure grammars[END_REF], which have been recently showed to be polynomially related in size to constant-height pushdown automata [START_REF] Guillon | Non-self-embedding grammars, constant-height pushdown automata, and limited automata[END_REF].

In this paper, we focus on standard pushdown automata, namely with an unrestricted pushdown store, that, however, are able to accept their inputs by making use only of a constant amount of the pushdown store. More precisely, we say that a pushdown automaton M accepts in constant height h, for some given h, if for each word in the language accepted by M there exists one accepting computation in which the maximum height reached by the store is bounded by h. Notice that this does not prevent the existence of accepting or rejecting computations using an unbounded pushdown height.

It is a simple observation that a pushdown automaton M accepting in constant height h can be converted into an equivalent constant-height pushdown automaton: in any configuration it is enough to keep track of the current height in order to stop and reject when a computation tries to exceed the height limit. The description of the resulting constant-height pushdown automaton has size polynomial in h and in the size of the description of M.

While studying these size relationships, we tried to understand how large can h be with respect to the size of the description of M. We discovered that h can be arbitrarily large. Indeed, in the first part of the paper we prove that there is no recursive function bounding the maximal height reached by the pushdown store in a pushdown automaton accepting in constant height, with respect to the size of its description. We also prove that it cannot be decided if a pushdown automaton accepts in constant height.

In the second part of the paper we restrict the attention to the case of pushdown automata with a one-letter input alphabet, namely unary pushdown automata. By studying the structure of the computations of these devices, we are able to prove that, in contrast to the general case, it can be decided whether or not they accept in constant height. Furthermore, we also prove that if a unary pushdown automaton M accepts in height h, constant with respect to the input length, then h can be bounded by an exponential function in the size of M. By presenting a suitable family of pushdown automata, we show that this bound cannot be reduced.

In the final part of the paper, we consider pushdown automata that accept using height which is not constant in the input length. Our aim is to investigate how the pushdown height grows. In particular, we want to know if there exists a minimum growth of the pushdown height, with respect to the length of the input, when it is not constant. The answer to this question is already known and it derives from results on Turing machines: the height of the store should grow at least as a double logarithmic function [START_REF] Alberts | Space complexity of alternating Turing machines[END_REF]. This lower bound cannot be increased, because a matching upper bound recently obtained in [START_REF] Bednárová | New results on the minimum amount of useful space[END_REF]. As a consequence of the constructions presented in the second part of the paper, we are able to prove that in the unary case this lower bound is logarithmic. We also show that it cannot be further increased.

For brevity reasons, many of the proofs are only outlined in this version of the paper.

Preliminaries

We assume the reader familiar with the standard notions from formal language and automata theory as presented in classical textbooks, e.g., [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]. As usual, the cardinality of a set S is denoted by #S, the length of a string x is denoted by |x|, the empty string is denoted by ε.

We first recall the notion of pushdown automata and present the form for these devices that will be used in the paper. A pushdown automaton (pda, for short) is a tuple M = Q, Σ, Γ, δ, q 0 , Z 0 , F where Q is the finite set of states, Σ is the input alphabet, Γ is the pushdown alphabet, q 0 ∈ Q is the initial state, Z 0 ∈ Γ is the start symbol, F ⊆ Q is the set of final states. Without loss of generality, we make the following assumptions about pdas:

1. at the start of the computation the pushdown store contains only the start symbol Z 0 , being at height 0; this symbol is never pushed on or popped off the stack; 2. the input is accepted if and only if the automaton reaches a final state, the pushdown store contains only Z 0 and all the input has been scanned; 3. if the automaton moves the input head, then no operations are performed on the stack; 4. every push adds exactly one symbol on the stack.

Note that the transition function δ of a pda M can be written as

δ : Q × (Σ ∪ {ε}) × Γ → 2 Q×({-,pop}∪{push(A)|A∈Γ }) .
In particular, for q, p ∈ Q, A, B ∈ Γ , σ ∈ Σ, (p, -) ∈ δ(q, σ, A) means that the pda M, in the state q, with A at the top of the stack, by consuming the input σ, can reach the state p without changing the stack contents; (p, pop) ∈ δ(q, ε, A) ((p, push(B)) ∈ δ(q, ε, A), (p, -) ∈ δ(q, ε, A), respectively) means that M, in the state q, with A at the top of the stack, without reading any input symbol, can reach the state p by popping off the stack the symbol A on the top (by pushing the symbol B on the top of the stack, without changing the stack, respectively). Now we present the main measure we consider in the paper, namely the pushdown height. The height of a pda M in a given configuration is the number of symbols in the pushdown store besides the start symbol Z 0 . Hence, in the initial and in the accepting configurations the height is 0. The height in a computation C is the maximum height reached in the configurations occurring in C.

We say that M uses height h(x) on an accepted input x ∈ Σ * if and only if h(x) is the minimum pushdown height necessary to accept x, namely, there exists a computation accepting x using pushdown height h(x), and no computations accepting x using height less than h(x). Moreover, if x is rejected then h(x) = 0. To study pushdown height with respect to input lengths, we consider the worst case among all possible inputs of the same length. Hence, we define h(n) = max {h(x) | x ∈ Σ * , |x| = n}. When there is a constant H such that, for each n, h(n) is bounded by H, we say that M accepts in constant height. Each pda accepting in constant height can be easily transformed into an equivalent finite automaton. So the language accepted by it is regular.

In the following, by the size of a pda we mean the length of its description. Notice that for each pda in the above-defined form, over a fixed input alphabet Σ, the size is polynomial in the cardinalities of the set of states and of the pushdown alphabet. 1We now present some technical notions that will be useful in order to state our results. Let M = Q, Σ, Γ, δ, q 0 , Z 0 , F be a fixed pda.

A surface pair is defined by a state q ∈ Q and a symbol A ∈ Γ , and it is denoted by [qA]. The surface pair in a given configuration is defined by the current state and the topmost stack symbol, namely the only part of the stack which is relevant in order to decide the next move.

A surface triple is defined by two states q, p ∈ Q and a symbol A ∈ Γ , and it is denoted by [qAp]. Surface triples are used to study parts of computations starting and ending at the same pushdown height and that do not go below that height in between. More precisely, a [qAp]-computation on an input string x ∈ Σ * is a computation C which starts from the state q with A on the top of the pushdown at some height h and the input head on the tape cell containing the leftmost symbol of x, and ends in the state p with A on the top of the pushdown at the same height h and the input head on the cell to the right of the cell containing the rightmost symbol of x, without reaching pushdown height less than h in between. We also say that C consumes the input x. We point out that, during C, the symbol A at height h is never replaced and C does not depend on h and on the symbols in the pushdown store at height less than h. The stack increment during C is the difference between the maximum stack height in C and the stack height at the beginning and at the end of C. Notice that the surface pairs at the beginning and at the end of C are [qA] and [pA].

We denote by L [qAp] the set of input strings consumed in all possible [qAp]computations. By suitably modifying M, we can obtain a pda accepting L [qAp] which, hence, is context free.

An horizontal loop on a surface pair [qA] is any [qAq]-computation consuming at least one input symbol. By considering a computation of 0 moves, we always have ε ∈ L [qAq] . Hence [qA] has a horizontal loop when L [qAq] contains at least one more string.

If a [qAp]-computation C contains a proper [qAp]-subcomputation C , for the same triple [qAp], which starts with stack higher than at the beginning of C, then the pair (X , Y) where X is the prefix of C ending in the first configuration of C , and Y is the suffix of C starting from the last configuration of C , is called vertical loop. Notice that at the end of X a nonempty string Aα is on the pushdown above the occurrence of A which was on the top at the beginning of C, and such a string is popped off during Y.

It is well known that context-free languages defined over a one-letter alphabet are regular [START_REF] Ginsburg | Two families of languages related to ALGOL[END_REF]. The size costs of the conversions of unary pdas and context-free grammars into equivalent finite automata have been studied in [START_REF] Pighizzini | Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds[END_REF].

Undecidability and Non-Recursive Bounds

In this section we prove that it cannot be decided whether a pda accepts in constant height or not. Furthermore, the trade-off between the sizes of pdas accepting in constant height and the maximal heights that are reached by their pushdown stores is not recursive. These results are proved by using a technique introduced in [8], based on suitable encodings of single-tape Turing machine computations. Roughly, configurations of a such machine T with state set Q and alphabet Γ are denoted in a standard way as strings from Γ * QΓ * . A computation consisting of m configurations α 1 , α 2 , . . . , α m is encoded as a string of blocks, separated by a delimiter $ / ∈ Q ∪ Γ , where the ith block is α i when i is odd, α R i when i is even (in the following, we use α (R) i to denote either α R i or α i according to the parity of the index i). Hence, the (encoding of a) valid computation of T on input w is a string

C = α 1 $α R 2 $α 3 $α R 4 $ • • • $α (R)
m , for some integer m ≥ 1 such that: 1. α i ∈ Γ * QΓ * , i.e., α i encodes a configuration of T , i = 1, . . . , 2. α 1 encodes the initial configuration on input w; 3. α i+1 is reachable in one step from α i , i = 1, . . . , m -1; 4. α m is a halting configuration of T .

A partial valid computation is defined in a similar way, by dropping Condition 4.

As proved in [8], the complement of the set of all valid computations of T is a context-free language.

Theorem 1. It is undecidable whether a pda accepts in constant height. 2Proof. (outline) We give a reduction from the halting problem. Let T be a deterministic Turing machine. With an easy modification, we suppose that arbitrarily long computations use arbitrarily large amounts of tape.

Given an input w, let α 1 , α 2 , . . . be the (possibly infinite) sequence of configurations in the computation of T on w. By adapting the techniques used in [8] to prove the above mentioned result, we describe a pda M T,w accepting the complement of the language partial(T, w) of partial computations of T on w.

Given an input

D = β 1 $β R 2 $ • • • $β (R)
r , with β i ∈ (Q ∪ Γ ) * , i = 1, . . . , r, M T,w guesses which one among Conditions 1, 2 and 3 is not satisfied. For the first two conditions, the finite control is sufficient. For the third condition, M T,w nondeterministically selects one block β (R) i , 1 ≤ i ≤ r, copies it on the pushdown store and checks the condition by scanning the (i + 1)th block, if any, while suitably comparing it with the block just saved on the store. (If i = r then the verification fails.) Suppose that D satisfies Conditions 1 and 2, but not Condition 3. Then, there is a computation which accepts D using pushdown height equal to the length of the first block β (R) i for which the condition is not satisfied, i.e., the block corresponding to the largest i such that β j = α j for j = 1, . . . , i. Since the pushdown height used to accept a string x is defined as the minimum pushdown height in accepting computations on x, we conclude that the pushdown height used to accept D is bounded by |α i |. So, if T halts on w, then the maximum amount of the pushdown store used to accept a string in (partial(T, w)) c is bounded by the length of the largest configuration reached by T on w. Otherwise, for each integer h, any string

α 1 $α R 2 $ • • • α i $β R , where i is odd, |α i | ≥ h, β ∈ Γ * QΓ * ,
and β = α i+1 , requires height at least h to be accepted.

Hence, T halts on w if and only if M T,w accepts in constant height.

As already observed in the introduction, any pda M accepting in constant height h can be converted into an equivalent constant-height pda. From such a machine, equivalent nfas and dfas with a number of states exponential and double exponential in h, respectively, are easily obtained. In the worst case these bounds cannot be reduced [START_REF] Geffert | More concise representation of regular languages by automata and regular expressions[END_REF]. We now show that, however, h cannot be bounded by any recursive function in the size of M.

Theorem 2. For any recursive function f : N → N and for infinitely many integers n there exists a pda of size n accepting in constant height H(n), where H(n) cannot be bounded by f (n). 3Proof. (outline) The argument is derived from [START_REF] Meyer | Economy of description by automata, grammars, and formal systems[END_REF]Prop. 7]. For n > 0, let BB n be a busy beaver with a set of n states Q n and tape alphabet Γ = {1, b}, namely a single-tape deterministic Turing machine that, starting with an empty tape, ends the computation with a string on the tape in which the number of 1s, denoted as Σ(n), is maximum. It is known that Σ(n) cannot be bounded by any recursive function [START_REF] Rado | On non-computable functions[END_REF]. Hence, also the maximal length of configurations occurring in such a computation cannot be bounded by any recursive function.

Let C n be the encoding of the valid computation of BB n on ε. By adapting the arguments used to prove Theorem 1, we can define a pda M n , whose description has a size polynomial in n, which accepts all the strings over (Q n ∪ Γ ∪ {$}) * different from C n , and such that each string different from C n is accepted using height bounded by the length of the longest configuration occurring in C n . Since n is fixed, M n accepts in constant height. Furthermore, by suitably modifying C n , we can obtain a string that requires height equal to the maximal length of configurations occurring in C n to be accepted by M n .

This allows to conclude that the pushdown height used by M n cannot be bounded by any recursive function in the size of M n .

Corollary 1. There is no recursive function bounding the size blowup from pdas accepting in constant height to finite automata.

Constant Height Decidability in the Unary Case

In Section 3 we proved that it cannot be decided if a pda accepts in constant height. This section is devoted to showing that this property turns out to be decidable in the restricted case of pdas with a one-letter input alphabet. We first give an informal outline of the argument.

Any accepting computation on a sufficiently long input should contain horizontal or vertical loops. The use of vertical loops can lead to computations using unbounded height. However, we prove that if an accepting computation on an input a visits a surface pair on which there exists a horizontal loop, then there is another accepting computation for the same input in which almost all occurrences of the vertical loops are replaced by occurrences of such horizontal loop. The number of vertical loops which remain in the resulting computation is bounded by a constant. As a consequence, the amount of pushdown store sufficient to accept a is also bounded by a constant. In contrast, when all accepting computations on a long string a do not visit any surface pair having a horizontal loop, vertical loops and an increasing of the stack cannot be avoided. Hence, the given pda works in constant height if and only if the cardinality of L v \ L h is finite, where L h (L v , resp.) is the set of strings which are accepted by a computation visiting a (not visiting any, resp.) surface pair having a horizontal loop. Since we are considering a unary alphabet, languages L v and L h are regular. So the finiteness of their difference is decidable. To obtain these results, we refine some of the arguments given in [START_REF] Pighizzini | Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds[END_REF] to study the size costs of the transformations of unary context-free grammars and pushdown automata into equivalent finite automata.

Loops and grammars

Let G = V, Σ, P, S be a context-free grammar in binary normal form, an extension of Chomsky normal form where, besides productions A → BC and A → a, also unit productions A → B and ε-productions are allowed. Let v = #V be the number of variables of G.

If T is a parse tree whose root is labeled with a variable A ∈ V and such that the labels of the leaves, from left to right, form a string α ∈ (V ∪ Σ) * , then we write T : A ⇒ α. Furthermore, we indicate by ν(T ) the set of variables occurring as labels of the nodes in T . As usual, the height of a derivation tree T is the maximum number of edges from the root to a leaf of T . A gap tree from a variable A ∈ V , also called A-gap tree, is a tree corresponding to a nonempty derivation of the form A + ⇒ xAy, with x, y ∈ Σ * . Let us suppose that G is unary, i.e., Σ = {a}. The following lemma will be crucial to obtain the main result of this section. It states that each long enough string a in the language generated by G can be derived by pumping a derivation tree of some short string by many occurrences of a same gap tree. Furthermore, such a gap tree can be arbitrarily chosen among the A-gap trees generating "short" nonempty strings, with A occurring in the derivation of a . Lemma 1. For any derivation tree T : S ⇒ a and for any A-gap tree T A : A ⇒ a i Aa j , with 0 < i + j ≤ 2 v 2 -2 v 2 -v and A ∈ ν(T ), there exists a derivation tree T : S ⇒ a which is obtained by pumping a tree

T 0 : S ⇒ a 0 such that ν(T 0 ) = ν(T ), 0 ≤ 0 ≤ 2 v 2 -1 + (2 v 2 -2 v 2 -v ) 2 , with k ≥ 0 occurrences of T A .
Proof. (outline) First, the tree T is "un-pumped" by removing several gap trees, up to find a tree T r : S ⇒ a r , with r ≤ 2 v 2 -1 and ν(T r ) = ν(T ). The tree T r is then "re-pumped" to get T 0 , by using a number bounded by a constant of occurrences of the removed gap trees. The tree T , which generates the same string as the original T , can be obtained by pumping T 0 with a suitable number of occurrences of T A . The possibility of doing these transformations, which finally produce a different tree for the same string, derives from a result related to Diophantine equations [START_REF] Mereghetti | Optimal simulations between unary automata[END_REF]Lemma 2.6] and from the fact that in the unary case terminal symbols commute.

Simulating vertical loops by a horizontal loop

Let us consider a fixed (not necessarily unary) pda M = Q, Σ, Γ, δ, q 0 , Z 0 , F . We define the grammar G = V, Σ, P, S , where the elements of V are triples [qAp], with q, p ∈ Q, A ∈ Γ , plus the start symbol S (hence v = #V = 1 + (#Q) 2 • #Γ ), and P contains the following productions:

1. [qAp] → [qAr][rAp], for q, p, r ∈ Q, A ∈ Γ ; 2. [qAp] → [q Bp ], for q, q , p, p ∈ Q, A, B ∈ Γ such that (q , push(B)) ∈ δ(q, ε, A) and (p, pop) ∈ δ(p , ε, B); 3. [qAp] → σ, for q, p ∈ Q, σ ∈ Σ ∪ {ε}, A ∈ Γ such that (p, -) ∈ δ(q, σ, A); 4. [qAq] → ε, for q ∈ Q, A ∈ Γ ; 5. S → [q 0 Z 0 q], for q ∈ F .
Applying standard techniques, we can prove that G generates the language accepted by M. Since we are interested in the amount of stack used by M, we state such equivalence in a stronger form, which also considers the use of the stack in the computations. In particular, we relate the stack increment to the unit production height which, for a derivation tree T of the above grammar G, is defined as the maximum number of edges corresponding to unit productions in a path from the root to a leaf in T . As a consequence of a technical lemma, which is omitted, we obtain: Corollary 2. For any integer h ≥ 0, a string x is accepted by M using pushdown height h if and only if there is a derivation tree T of x in G with unit production height h.

Let us restrict to the unary case. Using Corollary 2, we can reformulate Lemma 1 in terms of pushdown automata. Roughly, we can say that for each computation C accepting a "long" input, there is another computation accepting the same input, which is obtained by pumping a suitable computation C 0 , chosen from a finite set, with a repeated pattern which is arbitrarily selected from another finite set that depends on C 0 . We will use this property to replace in an accepting computation C almost all the vertical loops with many occurrences of a horizontal loop, in the case a surface pair [rB] having a horizontal loop occurs in C. In this way, we will be able to obtain an accepting computation on the same input using a bounded amount of pushdown storage. Theorem 3. Let C be an accepting computation on input a which visits a surface pair [rB] having a horizontal loop. Then there exists another accepting computation on a which uses pushdown height at most 2 O(v 2 ) .

Proof. (outline) First, we observe that if C visits the surface pair [rB] then there exists a derivation tree T : S ⇒ a with [rBr] ∈ ν(G). In fact, one According to Theorem 3, all strings in L h are accepted in constant height 2 O(v 2 ) .

If the set L v \ L h is infinite, then it should contain arbitrarily long strings. It can be verified that an arbitrarily high stack is required to accept them.

Otherwise, M accepts in constant height. In this case, we evaluate the height of the stack used to accept the strings in L v \ L h . We can modify M to obtain pdas M v and M h accepting languages L v and L h , respectively. According to Corollary 2 in [START_REF] Pighizzini | Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds[END_REF], these automata can be converted into equivalent dfas with 2 O(v 2 ) states. Hence L v \ L h , which is finite, is accepted by a dfa with less than 2 O(v 2 ) states. So, the longest string in L v \ L h has length at most 2 O(v 2 ) . This implies that each string in L v \L h is accepted by M using height 2 O(v 2 ) . Corollary 3. It is decidable whether a unary pda accepts in constant height.

Size versus Height in the Unary Case

The arguments used in Section 4 to prove that it is decidable whether a unary pda A accepts in constant height, give an exponential upper bound for the maximum stack height, with respect to the size of A. We can prove that such an exponential bound cannot be reduced: Theorem 5. For each integer k > 0 there exists a pda M k having a size polynomial in k and accepting in height which is constant with respect to the input length but exponential in k.

Proof. (outline) For each integer k > 0, let us consider the language H k = {a t | t = α2 k + β(2 k + 1), α, β ≥ 0}. We can define a pda M k of size O(k) which accepts each string in H k by computations consisting of two parts. In the first part, a horizontal loop which consumes 2 k input symbols is repeated an arbitrary number α ≥ 0 of times. This uses constant height O(k). In the second part, a vertical loop consuming 2 k +1 input symbols occurs β ≥ 0 times, using height β+ k -1. According to Theorem 3, each accepting computation can be replaced by an equivalent accepting computation in which the number of occurrences of the vertical loop is bounded by a constant. Hence M k accepts in constant height.

However, an height exponential in k is necessary. In fact, let a t ∈ H k be the string obtained by choosing α = 0 and β = 2 k -1, namely, t = (2 k -1)(2 k + 1). We can prove that the only solution of the equation t = α 2 k + β (2 k + 1), with integers α , β ≥ 0 is α = α = 0 and β = β = 2 k -1. This allows to conclude that the only accepting computation on a t is the one which uses height β + k -1 ≥ 2 k . Hence, to accept a t an exponential height, with respect the size of M k , is necessary.

An Optimal Lower Bound for Non-Constant Height

In this section we turn our attention to pdas accepting in non-constant height. It is known that in this case the height of the pushdown store should grow at least as the function log log n, with respect to the input length n [START_REF] Alberts | Space complexity of alternating Turing machines[END_REF]. Furthermore, this lower bound is optimal [START_REF] Bednárová | New results on the minimum amount of useful space[END_REF]. We show that in the unary case the optimal bound increases to a logarithmic function.

Let us start by proving the lower bound: Theorem 6. Let M be a unary pda using height h(n). Then either h(n) is bounded by a constant or there exists c > 0 such that h(n) ≥ c log n infinitely often.

Proof. (outline) According to the proof of Theorem 4, if h(n) is not constant, then there exist infinitely many strings in L v \L h that are accepted only by computations that use vertical loops and do not visit surface pairs having horizontal loops. Let M v be the pda accepting L v and, for a n ∈ L v \ L h , M h(n) be the pda obtained by bounding the height of the pushdown of M v to h(n).

Using Corollary 2 in [START_REF] Pighizzini | Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds[END_REF], we can prove that there exists an nfa N h(n) equivalent to M h(n) whose number of states is bounded by 2 d•h(n)+1 + 1, where

d = 2 • (#Q) 2 • #Γ .
Since M h(n) has stack height bounded by h(n), it cannot have vertical loops. Furthermore, accepting computations of M v do not use surface pairs with horizontal loops. Hence, the language accepted by M h(n) is finite. Thus, in N h(n) the string a n is accepted by a path without any repeated state. This implies that N h(n) must have more than n states.

Given any constant c, if h(n) < c log n, then the number of states of N h(n) would be 2 d•h(n)+1 + 1 < 2 d•c log n+1 + 1 = 2n d•c + 1. For c sufficiently small, e.g., c < 1/(2d), we get that the number of states of N h(n) is less than n, provided that n is not too small. This gives a contradiction. Hence, it must exist a constant c such that h(n) ≥ c log n infinitely often.

We now prove a matching upper bound: Theorem 7. There exists a unary pda accepting every word a , > 0, using pushdown height exactly log 2 + 1 and the empty word using height 0.

Proof. (outline) Consider the pda A = Q, {a}, Γ, δ, q I , Z 0 , {q F } , where Q = {q I , q 1 , q 2 , q F }, Γ = {Z 0 , 0, 1}, and δ defined as follows, for X ∈ Γ :

1. δ(q I , ε, X) = (q F , -); 2. δ(q I , ε, X) = (q I , push(0)); 3. δ(q F , ε, 0) = (q 1 , pop); 4. δ(q 1 , a, X) = (q 2 , -); 5. δ(q 2 , ε, X) = (q I , push(1)); 6. δ(q F , ε, 1) = (q F , pop). From the initial state q I , the pda A can reach the final state q F with the same pushdown height either with an ε-move (Transition 1) or by using a computation path making two recursive calls and consuming one input symbol as depicted in Figure 1. Each string in a * is accepted by A. Furthermore, pushdown height h is necessary and sufficient to accept all strings of length , with 2 h-1 ≤ < 2 h .

Fig. 1 .

 1 Fig. 1. The evolution of the pushdown store of A during the recursive subroutine leading from qI to qF , when recursive calls are made. The dashed lines should be replaced either by an ε-move or, recursively, by the same pattern.

In some papers pdas are presented in different forms. As pointed out in[START_REF] Bednárová | Removing nondeterminism in constant height pushdown automata[END_REF], it is possible to turn the definition of pdas into these equivalent forms, with a polynomial increase in size and by preserving the property of being constant height.

We point out that for unambiguous pdas, the property is decidable[START_REF] Malcher | Descriptional complexity of pushdown store languages[END_REF].

Notice that here H(n) is a function of the size of the pda and not of the input.

of the triples [rBs] or [sBr] for some s ∈ Q should appear in the derivation tree corresponding to C. Since G contains the productions [rBs] → [rBr][rBs],

[sBr] → [sBr][rBr] and [rBr] → ε, we can suitably modify the tree in order to introduce one occurrence of [rBr], without changing the derived string. Now we select a [rBr]-gap tree T [rBr] deriving a "short" non empty string, i.e.,

According to Lemma 1, we can obtain another tree T : S ⇒ a by pumping a tree T 0 : S ⇒ a 0 , such that ν(T

We observe that in the tree T the k occurrences of T [rBr] could be nested, possibly giving a stack height in the corresponding computation which linearly increases with k. To fix this problem, we modify T as we now describe.

Let u be a node of T 0 labeled by [rBr] and T u be the subtree of T 0 rooted at u, such that T 0 is pumped starting from u with t > 1 nested occurrences of T [rBr] . We rearrange these t occurrences of T [rBr] in a sequence by inserting, starting from node u, a subtree corresponding to a derivation [rBr] ⇒ [rBr] t obtained by using t -1 times the production [rBr] → [rBr][rBr]. To each leaf of this subtree we append one occurrence of the [rBr]-gap tree T [rBr] . Finally, to the leaf labeled [rBr] of the first occurrence of T [rBr] we append the tree T u , and to each of the remaining t -1 leaves labeled [rBr] we append one leaf labeled with the empty word.

Let T be the tree obtained after this modification, which still generates a . Using Corollary 2 we now estimate the amount of pushdown store used in the computation C corresponding to T . The unit production height of T is bounded by the maximum number h 0 of such edges in a path in T 0 plus the maximum number h 1 of such edges in a path in T [rBr] which, in turn, are bounded by the height of T 0 and T [rBr] , respectively. We can prove that h 0 + h 1 is 2 O(v 2 ) . According to Corollary 2, this allows us to conclude that a is accepted by a computation which uses pushdown height 2 O(v 2 ) .

Decidability

We are now able to prove the main result of this section: Theorem 4. Let M be a unary pda with n states and m pushdown symbols. Then M accepts in constant height if and only if it accepts in height bounded by 2 O(v 2 ) , where v = n 2 m + 1.

Proof. (outline) Let L be the language accepted by M. We also consider the following two languages L h and L v , whose union gives L:

-L h is the set of strings accepted by the computations of M which visit at least one surface pair having a horizontal loop. -L v is the set of strings accepted by the computations of M which visit only surface pairs that do not have horizontal loops.


Charlotte Allard

Raffaela Nascimento

Frederic Fossard

Léonard Schué

Emmanuel Flahaut

Annick Loiseau

Patrick Desjardins

Richard Martel
email: r.martel@umontreal.ca

Étienne Gaufrès

Raffaela Nascimento

Frederic Fossard

Leonard Schué

Etienne Gaufres
email: etienne.gaufres@u-bordeaux.fr

Rafaella Nascimento

Frédéric Fossard

Léonard Schué

Etienne Gaufrès

Dyes@BNNT Nanohybrids for Photostable Fluorescence Imaging

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

intersystem crossing [START_REF] Widengren | Fluorescence Correlation Spectroscopy of triplet states in solution: A theoretical and experimental study[END_REF][START_REF] Kasha | Characterization of electronic transitions in complex molecules[END_REF] , molecular conformation change [START_REF] Di Paolo | Photoisomerization Dynamics and spectroscopy of the Polymethine Dyes DTCI[END_REF] , and light-induced charging, resulting in temporary perturbations (blinking) due to random excursions between bright and dark states [START_REF] Moerner | Illuminating single molecules in condensed matter[END_REF][START_REF] Efros | Random Telegraph Signal in the Photoluminescence Intensity of a Single Quantum Dot[END_REF][START_REF] Galland | Two types of luminescence blinking revealed by spectroelectrochemistry of single quantum dots[END_REF] .

More significantly, oxidizing species (ROS) placed in contact with the dye induce irreversible photoluminescence (PL) extinction, known as photobleaching or fading [START_REF] Widengren | Mechanism of photobleaching investigated by fluorescence correlation spectroscopy[END_REF][START_REF] Stennett | Photophysical processes in single molecule organic fluorescent probes[END_REF] . The processes drastically reduce the time window to perform experiments and limit more particularly bioimaging applications such as in-vivo monitoring in various conditions. For example, the green fluorescent protein (GFP) provides a limited number of absorption/emission cycles in the range between 10 4 to 10 5 emitted photons before photo-bleaching. GFPs remain nevertheless very popular as fluorescence probes, but their use is limited to only a few minutes in typical imaging conditions [START_REF] Diaspro | Handbook of Biological Confocal Microscopy[END_REF][START_REF] White | Photobleaching GFP reveals protein dynamics inside live cells[END_REF] .

Expedients to delay photobleaching have been developed and good examples include the addition of oxygen-blocking molecules, such as anoxia [START_REF] Bernas | Minimizing photobleaching during confocal microscopy of fluorescent probes bound to chromatin: role of anoxia and photon flux[END_REF] , and a passivation of the dyes against ROS by a polymer, a porous material, or a supramolecular assembly [START_REF] Thomsson | Cyclodextrin Insulation Prevents Static Quenching of Conjugated Polymer Fluorescence at the Single Molecule Level[END_REF][START_REF] Lee | Fabrication of Photoluminescent Dyes/Poly (acrylonitrile) Coaxial Nanotubes Using Vapor Deposition Polymerization[END_REF][START_REF] Frampton | Insulated Molecular Wires[END_REF] . These approaches have had, however, a limited success due to the size increase around the dyes and loss of brightness from the presence of quenchers in the passivation layers. As an example, inorganic calcium phosphate nanoparticles mixed with dyes (called FloDots) have been developed to prepare photostable fluorescence probes for imaging [START_REF] Yao | FloDots: luminescent nanoparticles[END_REF] , but the size constraints (10 -120 nm) limit the diffusion properties of the probe.

Inspired by these passivation strategies and recent advances on the encapsulation of organic dyes inside single-walled carbon nanotubes [START_REF] Yanagi | Highly Stabilized b-Carotene in Carbon Nanotubes[END_REF][START_REF] Loi | Encapsulated of conjugated oligomers in single-walled carbon nanotubes towards nanohybrids for photonic devices[END_REF][START_REF] Gaufrès | Giant raman scattering from J-aggregated dyes inside carbon nanotubes for multispectral imaging[END_REF][START_REF] Cambré | Asymetric dyes align inside carbon nanotubes to yield a large nonlinear optical response[END_REF] (SWCNTs), we have explored the use of nanotubes as an alternative host to passivate dyes from the environment while keeping both small (nanometer) sizes and good optical properties (e.g. brightness and stability). Because of efficient energy transfer processes between dyes and SWCNT hosts (E g < 1 eV), it become apparent that the PL of the dyes is readily quenched in most, if not all, of these nanohybrids [START_REF] Gaufrès | Aggregation control of α-Sexithiophene via isothermal encapsulation inside single-walled carbon nanotubes[END_REF][START_REF] Van Bezouw | Diameter-dependant optical absorption and excitation energy transfer from encapsulated dyes molecules toward single-walled carbon nanotubes[END_REF] . Hence, we turn our attention to the boron nitride nanotube (BNNT), which has a band gap energy (E g ~ 5.5 eV) that is large enough to be transparent within a wide range of wavelengths and quasi-independent from the chirality [START_REF] Blase | Stability and band gap constancy of boron nitride nanotubes[END_REF][START_REF] Arenal | Electron energy loss spectroscopy measurement of the optical gaps on individual boron nitride single-walled and multiwalled nanotubes[END_REF] . Herein, we report results on the preparation and on the chemical and photoluminescence properties of dyes encapsulated inside BNNTs (dyes@BNNTs). Our experiments on a-sexithiophene (6T) and derivatives of 3,6-Bis[2,2']bithiophenyl-5-yl-2,5-di-noc-tylpyrrolo [3,4-c]pyrrole-1,4-dione (DPP) encapsulated inside small diameter BNNTs (d inner < 3 nm) show a drastic improvement of the stability compared to free dyes against laser light exposure. We also observe effective passivation of the dyes against the environment, even under harsh chemical conditions. Using various imaging demonstrations with living organisms (Daphnia Pulex), we report on a reduced toxicity of the dye nanohybrid compared to free dyes and demonstrate their exceptional photostability as a nanoprobe for multi-modal bio-imaging in a wide range of wavelengths.

Results and discussions

Figure 1 schematizes the main synthesis steps of the dye nanohybrids along with the photoluminescence response obtained before and after the dye encapsulation. The synthesis begins by cutting raw BNNTs (BNNT LLC supplier) using mechanical grinding and ultrasound treatments. The resulting material is then purified in nitric acid and annealed at high temperature in air [START_REF] Chen | Purification of boron nitride nanotubes[END_REF] to suppress background PL from BN and B x O y impurities 27 (Supplementary Fig. 1). The last step is a liquid phase encapsulation of a selected dye molecule, e.g. DPP2 (Fig. 1a), in thus processed BNNTs, followed by a thorough rinsing in DMF/Toluene and finally with a piranha solution at room temperature to remove excess of dye molecules. The resulting solid can be dispersed in a solvent and yields a highly colored solution, such as shown in Fig. 1a andc.

The first signature of encapsulation is a clear color change compared to that of free dyes. In Fig. 1c, the coloration of the free 6T in DMF (P1) is compared to that of a mixture of 6T and BNNTs after an encapsulation step in toluene for 24 hours at 25°C (P2) and 115°C (P3). No change is observed between P1 and P2, whereas a clear color change from yellow to red is observed for P3.

As detailed below, the color shift indicates that the dyes have filled the BNNTs and the encapsulation is driven by temperature. Similar spectral changes of the dye resonance are also observed with other rod-like molecules. For example, the derivatives of 3,6-Bis[2,2']bithiophenyl-5-yl-2,5-di-n-oc-tylpyrrolo [3,4-c]pyrrole-1,4-dione (DPP2 and DPP3) are encapsulated using the same protocol but at 80°C (Fig. 1c and Supplementary Section 2.2). The behavior observed here with BNNTs is fully consistent with previous results of dye encapsulation in SWCNTs [START_REF] Gaufrès | Aggregation control of α-Sexithiophene via isothermal encapsulation inside single-walled carbon nanotubes[END_REF] . For both types of nanotubes, the process is endothermic, a behavior ascribed to a heat unbalance from intermolecular interactions between dyes (encapsulated) molecules and between dyes (free) and solvent molecules. Both a shift in color and an endothermic process of encapsulation imply realignment and aggregation of the dyes within the inner space of the nanotubes. In Figures 1b, we explore more quantitatively this transformation using different dye nanohybrids (P3, P5 and P7) in DMF compared to the solutions of the same dyes (free) in DMF (P1, P4, P6). For example, a solution of free 6Ts (P1) displays a photoluminescence line shape characterized by a strong 0-0 vibronic band.

In contrast, the 6T@BNNT solution (P3) displays a PL spectrum that is red-shifted and broadened to a point that vibronic bands become undistinguishable. Similar behavior is observed with DPP2 and DPP3 and DPP@BNNT solutions. A strong 0-0 vibronic band is related to energetic disorders between free molecules, which is typical of individualized dye molecules in polymers, such as polymethylmethacrylate [START_REF] Spano | Determining exciton coherence from the photoluminescence spectral line shape in poly(3-hexylthiophene) thin films[END_REF][START_REF] Ostrowski | The effect of aggregation on electronic and optical properties of oligothiophene particles[END_REF] (PMMA). For all of the dye nanohybrids tested so far, we observed no clear vibronic structure and a slight translucence of the solutions ascribed to molecular ordering (dye aggregation) and optical diffusion induced by the BNNT hosts.

The passivation of the encapsulated dyes with the crystalline dielectric sheath of the BNNT walls is tested next using stability measurements against photo-bleaching and chemical reaction. To do so, we compared in Fig. 2 the PL properties of free dyes with that of individual or small bundles of 6T@BNNTs deposited on an inert Si/SiO 2 substrate in ambient conditions. Note that an oxide thickness of ~300 nm is chosen to avoid destructive optical interference with the substrate. To gain statistics, a global hyperspectral imager (RIMA TM , Photon etc.) was used to photo-excite uniformly a large area of the sample (200x200 µm 2 ) with continuous laser light [START_REF] Gaufrès | Hyperspectral Raman imaging using Bragg filter of graphene and other low-dimensional materials[END_REF] at l ex = 532 nm. This configuration has given us a large statistical ensemble of measurements on individualized 6T@BNNT bundles as a function of exposure time and fluence conditions. As an example, Figure 2a shows a zoomed view of the PL image of a 5 µm long bundle at a laser fluence typical for bioimaging (1.2 µW.µm -2 ). In Figure 2b, the PL signal of the bundle, as a function of exposure time, shows no noticeable intensity loss, even after exposure for more than 8 hours in air. This interesting result indicates a clear resistance against photobleaching, which is also demonstrated with the DPP nanohybrids in Fig. 2b. The result contrasts with the fast fading PL signal (in red) of free dyes (not encapsulated) dispersed on the substrate. As expected and typical of photobleaching, the half lifetime of the integrated emission (t 1/2 ) of free dyes is only few minutes, whereas individual dyes@BNNT bundles produce unaltered PL after more than 30 hours, which is only limited here by our setup to a factor of 1x10 [START_REF] Kasha | Characterization of electronic transitions in complex molecules[END_REF] . Furthermore, PL imaging taken at the level of a single dye nanohybrid with a frame rate of 0.5 sec indicates no blinking under a fluence of 1.2 µW.µm -2 at l ex = 532 nm (Fig 2c). These photostability results are impressive considering that this is a lower bound estimate limited only by our setup.

The chemical stability of the dye nanohybrids is tested using individualized 6T@BNNT bundles deposited on Si/SiO 2 by exposure to an oxygen plasma of 100 W for 10 minutes. No significant change in the PL spectral shape and intensity is detected after treatment, whereas free 6T molecules on Si/SiO 2 have completely vanished (Fig. 2d). The enhanced stability of the encapsulated dyes has also been observed upon thermal annealing up to 350°C in air and using piranha solutions (not shown). These results demonstrate that the 6T@BNNT is far more stable than free 6T dyes. The chemical and physical stability experiments have been repeated on a number of dye nanohybrids of different lengths deposited on substrates or dispersed in a solution (See e.g. Supplementary Figs. 5 and6). All of the results share the same conclusion, which underlines the tremendous gain in stability due to dye confinement inside the 1D cavity of BNNTs. The time acquisition is 0.2 sec and the laser fluence is 1.2 µW.µm -2 . b, Time evolution of the integrated PL of isolated bundles of 6T@BNNTs and DPP2@BNNTs on a Si/SiO 2 surface, compared to free DPP2 photoexcited under a fluence of 1.2 µW.µm -2 at l ex = 532 nm (long pass filter at 533 nm). c, PL intensity recorded at time intervals of 0.5 sec. d, PL spectra (l ex = 473 nm) of free 6T and 6T@BNNT deposited on a substrate recorded before (left) and after (right) a 100 W treatment to oxygen plasma for 10 minutes.

The changes in optical and chemical properties of dye molecules, as reported in Figs 1 and2, stem from specific structural rearrangements of the dyes driven by the BNNT template. These morphological rearrangements of the dyes form aggregates that can be directly observed in High Resolution Transmission Electron Microscopy (HRTEM). Examples in Fig. 3 show images of 6T molecules encapsulated inside double-and multi-walled BNNTs deposited from solutions onto a Molybdenum-SiO 2 (Mo/SiO 2 ) TEM grid. More examples of HRTEM are also shown in Supplementary, Fig. S8. A progressive ordering of the 6T dyes from disordered assemblies to wellaligned individual molecules is observed for inner diameters (d inner ) going from 7 nm down to 0.9 nm, respectively (Fig. 3f). A key result for this study, which is shown schematically in Figure 3A, is the presence of single and double aggregates of 6T molecules in BNNTs having the smallest d inner . In Fig. 3f, these aggregates are nicely resolved as short sticks (pointing arrows) located inside BNNTs of d inner = 0.9 and 1.55 nm for single and double aggregates, respectively. It is clear from the images that high confinement (i.e. low d inner ) induces molecular ordering and alignment along the nanotube. A cavity of d inner = 4 nm is, for instance, much larger (about twice) than the length of the molecules and provides higher degrees of freedom to accommodate various assemblies, whereas d inner = 0.9 nm (the smallest diameter of our sample) provides just enough space to fit one molecule in a head-to-tail type of stacking.

To determine that the filling material is composed of 6T molecules, complementary experiments were performed using Scanning Transmission Electron Microscopy and Energy Electron Loss Spectroscopy (STEM-EELS) acquired at 80kV to gain information on the chemical composition (core-loss) and near-band edge response (low-loss) of the filling materials with a spatial resolution of around 2.5 nm (Supplementary Fig. 7). The HRTEM image in Fig. 3b for the HOMO-LUMO gap of 6T molecules and at 5.5 eV (region 2) for the BNNT band gap.

Consistent to other reports on similar oligothiophene encapsulation inside SWCNTs [START_REF] Loi | Encapsulated of conjugated oligomers in single-walled carbon nanotubes towards nanohybrids for photonic devices[END_REF][START_REF] Gaufrès | Giant raman scattering from J-aggregated dyes inside carbon nanotubes for multispectral imaging[END_REF][START_REF] Almadori | Chromophore ordering by confinement into carbon nanotubes[END_REF][START_REF] Belhboud | Enhancing the infrared response of carbon nanotubes from oligoquaterthiophene interactions[END_REF] , the results confirm the encapsulation of the 6Ts inside BNNTs. The assembly of dyes inside BNNTs into aligned and structured aggregates is consistent with the assembly behavior observed on elongated dyes encapsulated inside SWCNTs [START_REF] Loi | Encapsulated of conjugated oligomers in single-walled carbon nanotubes towards nanohybrids for photonic devices[END_REF][START_REF] Gaufrès | Giant raman scattering from J-aggregated dyes inside carbon nanotubes for multispectral imaging[END_REF][START_REF] Cambré | Asymetric dyes align inside carbon nanotubes to yield a large nonlinear optical response[END_REF][START_REF] Gaufrès | Aggregation control of α-Sexithiophene via isothermal encapsulation inside single-walled carbon nanotubes[END_REF][START_REF] Almadori | Chromophore ordering by confinement into carbon nanotubes[END_REF][START_REF] Skowron | Chemical Reactions of Molecules Promoted and Simultaneously Imaged by the Electron Beam in Transmission Electron Microscopy[END_REF] . The similarities between these systems are striking, as both provide higher stability against photodegradation and exposure to ROSs. As seen in the HRTEM images of Fig. 3f, the head-totail stacking of the encapsulated dyes in small diameter BNNTs corresponds to the dye morphology of the emblematic J-aggregate state, a highly emissive state. On the contrary and not seen in our samples, a face-to-face stacking is characteristic of a low emissive state, the Haggregate. These aggregation states greatly influence the photo-physical properties of the dyes though interaction due to e.g. interaction and energy shifts associated with Davidov splitting [START_REF] Jelley | Spectral absorption and fluorescence in the molecular state[END_REF][START_REF] Spano | Excitons in conjugated oligomers aggregates, films and crystals[END_REF] .

We suspect that the overall red shift observed in Fig. 1 originates from J-like aggregations of the confined dyes and that the broadening of the bands is due to the large distribution of d inner in our samples, as evidenced by HRTEM in Fig. 3. Hence, the broad PL envelopes observed with different dyes nanohybrids are most likely due to the size distribution of d inner , giving a convolution of an ensemble of individual emitters having each a specific spectrum and aggregation state.

Further PL work on dye nanohybrids with diameter sorted BNNTs will be required to analyze the vibronic fingerprints of each emitter as a function of confinement and ordering. Nevertheless, a sorting of the nanotubes by diameter appears a valid approach to control the aggregation state and emissive properties of the dyes.

The impressive robustness and fading free properties of the Dyes@BNNT are appealing for bioimaging applications. Figure 4 presents an example of the use of dye nanohybrids to make optical nanoprobes for imaging living Daphina Pulex organisms in water -see bright-field image in Figure 4a#1. Daphnia (also called water fleas) are common planktonic crustaceans, which find use as chemical sensors in ecotoxicology studies, thanks to their high sensitivity to water quality [START_REF] Siciliano | How Daphnia (Cladocera) assays may be use as bioindicators for health effects?[END_REF] . To acquire the bio-images (Fig. 4a#2-5), we first solubilized the prepared dye nanohybrids (dye@BNNT) in a water based living medium called FLAMES [START_REF] Celis-Salgado | The FLAMES: a new, softwaterculture and bioassay medium for Cladocera[END_REF] , using a poly (ethylene) glycol derivative (mPEG-DSPE) (Supplementary Section 2.9). We then performed a first incubation test by placing a Daphnia in different FLAMES containing either free 6T, only PEG-BNNTs, or PEGdyes@BNNTs in different concentrations (see Supplementary Table S1). After an incubation of only few minutes, all daphniids exposed to free 6T were found dead. This is consistent with the known toxicity of such dyes to living organisms, which was evidenced in the 20 th century by many studies on drugs or contrast agents [START_REF] Churchman | Intravenous use of dyes[END_REF] . On the contrary, all of the Daphnia assays incubated with both PEG-BNNT and PEG-dyes@BNNT remain alive and active after incubation times ranging from a few minutes to 36 hours at concentrations between 10 and 50 µg.ml -1 (see video in Supplementary Fig. 4). This underlines the multiple roles of the BNNT host: i) Stabilize the PL signal from the nanoprobe, ii) act as a protective barrier against ROS, and iii) reduce toxicity to the living organisms. Living daphniids were then imaged under a fluorescence microscope equipped with UBG filter and a 10X objective. Daphnia Pulex incubated with PEG-BNNTs (i.e. no dye, Fig. 4a#2 down) presents similar signal than that observed from non-incubated Daphnia (Fig. 4a#2 top). This natural blue-green signal originates from the auto-fluorescence of the tissues in FLAMES through the UBG filter, which disappears after death or after few minutes only of photobleaching. In contrast, Daphniids incubated with PEG-Dyes@BNNTs (Fig. 4a# (bottom #2), 6T@BNNTs (#3), DPP2@BNNTs (#4) and DPP3@BNNTs (#5). b, Luminescence intensity time-lapses of dyes@BNNTs, (i) in living conditions, (ii) in post-mortem conditions. c, Raman spectra at l ex = 532 nm taken in the region of the digestive tube of Daphnia for #3 and at l ex = 633 nm for #4 and #5. d, PL image of a living Daphnia collected at a wavelength of 900 nm using an excitation at l ex = 532 nm. Inset: Optical image of the Daphnia. The scale bar is 200 µm for images #1, #3-#5 and 400 µm for #2.

In a second set of experiments, we investigated the photo-stability of the nanoprobes during invivo PL imaging of Daphnia Pulex under continuous light excitation. Daphniids were maintained alive during the first 3 hours of the time-lapse by adding more FLAMES to maintain temperature and compensate water evaporation under the microscope. The PL intensity, recorded every 3 minutes at 6 different points of the digestive tube (Fig. 4a), remains flat with time, which indicates that bleaching is suppressed in such continuous photoexcitation despite the fact that the nanoprobes are being in close contact with the ROS present in the water-based medium of the digestive tube of Daphniids. The brief and temporary drops of signal at 1h and 3h are attributed to sudden movements of the Daphnia in the exiguous swimming pool under the microscope objective (Fig. 4b). Even after death, which is typically caused by a drying of the FLAMES medium, the signal of the dye nanohybrids remain stable for an additional 12 hours of continuous excitation/imaging without any noticeable loss of signal (Fig. 4b). Interestingly, the Raman spectra in Fig. 4c, recorded at the level of the digestive tube of Daphnia #4 and #5, show that the specific vibrational fingerprint of the encapsulated 6T (or DPP) in BNNTs remain intact. This signal can be readily extracted and identified from the luminescence signal, thanks to the resonance enhancement of the dyes at λ ex = 532 nm. This last experiment demonstrates that the encapsulated dyes are not altered in the digestive tube of the living Daphnia and that they are highly photo-stable, giving further statistics of the effective passivation by the BNNT hosts.

The capability to probe in-situ both the photoluminescence and Raman scattering of different nanoprobes over a timescale of many hours is an interesting aspect with dye nanohybrids for use as multimodal probes for bio-imaging. Similar to the work on carbon nanotubes based NIR nanoprobes [START_REF] Welsher | A route to brightly fluorescent carbon nanotubes for near-infrared imaging in mice[END_REF][START_REF] Welsher | Deep-tissue anatomical imaging of mice using carbon nanotube fluorophores in the second near-infrared window[END_REF][START_REF] Danné | Comparative Analysis of Photoluminescence and Up conversion Emission from Individual Carbon Nanotubes for Bioimaging Applications[END_REF][START_REF] Roxbury | Hyperspectral Microscopy of Near-Infrared Fluorescence Enables 17-Chirality Carbon Nanotube Imaging[END_REF] , which emit at wavelengths beyond 900 nm, we performed experiments using a NIR DPP3@BNNT incubated in Daphnia. By simply shifting dyes, we were able to extend the PL emission (Fig. 4d) to the NIR I optical bio-window [START_REF] Shi | Transmission in near-infrared windows for deep brain imaging[END_REF] . We trust that this simple approach can be expanded further to other dyes (even toxic) offering broad NIR emission wavelengths. This will provide probes for deeper analysis in the near-infrared optical windows [START_REF] Antaris | A small-molecule dye for NIR-II imaging[END_REF] . In addition, these dyes nanohybrids, because of their 1D architecture, have similar diffusion properties than SWCNTs, which are advantageous for studies in biological media [START_REF] Fakhri | Brownian motion of stiff filaments in a crowded environment[END_REF][START_REF] Godin | Single-nanotube tracking reveals the nanoscale organization of the extracellular space in the live brain[END_REF] .

Previous works on the functionalization of multi-walled BNNTs have shown that BNNTs are appropriate templates to develop active nanostructures, such as drug delivery and other bioinvestigations [START_REF] Velayudham | Noncovalent Functionalization of Boron Nitride Nanotubes with Poly( p-phenylene-ethynylene)s and Polythiophene[END_REF][START_REF] Ciofani | A simple approach to covalent functionalization of boron nitride nanotubes[END_REF][START_REF] Niskanen | Boron nitride nanotubes as vehicles for intracellular delivery of fluorescent drugs and probes[END_REF] . Here, we have highlighted the potential use of dyes@BNNT nanohybrids to make active nanoprobes with high brightness and exceptional stability and tunability. Building on the constantly evolving knowledge on BNNT materials, it is expected that the dye@BNNT nanohybrids will greatly impact bio-imaging by extending the acquisition time and optical windows into the NIR I and II to go deeper into the body of living organisms. Tailoring optical signatures with enhanced stability through the 1D aggregation of dyes inside BNNT will represent a paradigm shift in developing for instance new in-vivo and post mortem biological investigations that have not yet been possible due to the limitations of conventional fluorescence probes.

Methods

The boron nitride nanotubes (BNNT) used in this work are provided by BNNT TM . See Supplementary Section 2.1 and 2.2 for details on cleaning and encapsulation of BNNTs. Briefly, the BNNT powder was sonicated in dimethylformamide (DMF) until complete dispersion, and filtrated on a PTFE filter (0.2 µm pore size). The obtained film was annealed at 800°C for 2h under atmospheric conditions. About 5 mg of dyes and 20 mg of purified BNNTs were dispersed sequentially in 20 mL or 300 mL of toluene, depending on the dye used, by sonication. The solution was then refluxed at 80°C or 115°C, again depending of the dyes used, to activate the encapsulation. The solution was finally washed in toluene and DMF at least 10 times to remove the free dyes molecules, until the filtrate became colorless.

For experiments on individualized Dyes@BNNTs on surface, the Dyes@BNNTs were suspended in N,N-dimethylformamide (DMF) and diluted as needed, typically at a concentration of ~0.1 mg/mL. This solution was spin-coated at 3000 rpm on a cleaned Si/SiO 2 substrate with aminopropyltriethoxysilane (APTES) functionalization.

For experiment with Daphnia, an incubation solution was prepared by dispersing Dyes@BNNT in FLAMES culture medium at a concentration ranging from 5 to 100 µg/ml. Adult individuals of Daphnia Pulex (clones DISP 1312) were kept at 22°C in FLAMES with algae for 4 days before the experiment, allowing for a new reproducing cycle. Then, the specimens were transferred to a FLAMES medium algae-free and remained there for 1 day at minimum to clean the digestive system and limit any PL from algae during the images/time lapse acquisition. Daphniids are then placed in the incubation solution for the required time. More details on the experiments with Daphnia and characterizations of the samples are provided in Supplementary Section 2.9 and 3.

The AFM images were produced using a Dimension 3100 microscope. The Raman/PL measurements were taken from different set-up depending on the experiments and these instruments and conditions are summarized in Table S2. In summary, luminescence images and photobleaching experiments were performed at λ ex = 532 nm using the Raman/PL mapping system RIMA TM (Photon Etc) using a 100X objective and a laser power ranging from 0.5 µW.µm -2 to 80 µW.µm -2 . Other fluorescence images were acquired with an Olympus confocal microscope equipped with a U-RFL-T mercury light source, a BX-UCB controller and a DP71 digital camera.

The images were acquired with a 10X objective and UBG, TRITC and TXRED filters. The acquiring conditions were: Exposure time: 1/20 sec and ISO 200 sensitivity. Z-stack of 20 images to probe the volume of the Daphnia was acquired by confocal imaging and stacked using the Autoblend function in Phostoshop.

received. Oligothiophene derivatives such as 3,6-Bis-[2,2']bithiophenyl-5-yl-2,5-di-n-octylpyrrolo [3,4-c]pyrrole-1,4-dione (DPPX) were synthesized according to the procedure (1).

Experiments with

Methods

Cleaning the BNNTs.

Cleaning of BNNT powder

The BNNT powder was sonicated in dimethylformamide (DMF) until complete dispersion (~2h), and filtrated on a PTFE filter (0.2 µm pore size). The obtained film was annealed at 800°C for 2h under atmospheric conditions. After the cleaning procedure, the parasite luminescence signal from BN impurities, B 2 O 3 , and defects became negligible. (see figure S1) Figure S1: Photoluminescence spectra of BNNT deposited on Si/SiO 2 before and after purification. Each spectrum corresponds to the average contribution from 5 areas on each sample. The wavelength excitation is 532 nm.

Encapsulation of sexithiophene (6T) and DPP molecules in BNNT powder.

6T@BNNT: In a typical experiment, 5 mg of 6T was added to 300 mL of toluene and dispersed by a mix of stirring and sonication. 20 mg of purified BNNT powder was added to the encapsulation solution and refluxed at 115°C (6T) for 24 h. The solution was then washed in toluene and DMF at least 10 times to remove the free 6T, until the filtrate became colorless. Finally, the sample was dispersed in DMF at the appropriate concentration for subsequent characterization. DPPx@BNNT: 5 mg of DPPX was solubilized in 20 mL of toluene and 5 mg of purified BNNTs were added to the encapsulation solution. The solution was sonicated for 30 minutes and refluxed at 80°C overnight. The washing and dispersion steps are as described above.

2.3 Aminopropyltriethoxysilane substrates (APTES) on silicon/silicon oxide. The substrates were cleaned by successive sonication of 10 minutes each in acetone and isopropanol (IPA). The substrates were then immersed in piranha solution for 20 min, rinsed in water, and dried with N 2 . Finally, the substrates were placed on glass slides suspended above a crystallization dish containing 1 mL of APTES. The desiccator was vacuum pumped for one minute and the chamber was sealed for an additional thirty seconds. The APTES layer was annealed in air for 45 minutes at about 100 ºC in a conventional oven.

Deposition of BNNTs on APTES substrate.

Raw BNNTs were suspended in N,N-dimethylformamide (DMF) and diluted as needed, typically at a concentration of ~0.1 mg/mL. This solution was spin-coated at 3000 rpm on a Daphniids were divided into 3 control groups, and 5 additional groups as described in the Table S1 below. Daphniids were transferred to 8 vials according to Table S1. S.9 ** After the excess of aggregation of the probes 6T@BNNTs-mPEG-DSPE, we decided to limit the maximum concentration to 50ug/mL C) PL measurements of 6T, 6T@BNNTs, DPPX@ BNNTs and BNNTs with Daphnia Pulex:

To perform the PL measurements, each Daphnia was transferred with the incubation medium to a glass slide. The excess of liquid was dried out in order to keep the minimum necessary to maintain Daphnia alive. Following, movies of the PL from dyes@BNNTs in Daphnia were acquired using a UBG filter. Longer PL measurements (from t=0 to t=12 hours) had a duplicate slide on which the liquid was dried out and daphniids were kept in air.

The NIR PL image in Figure 4D was performed using a Daphnia individual incubated with DPP3@BNNTs (5 µg/ml) and recorded using the Hyperspectral Raman/PL Imager -RIMA TM from Photon etc (laser power of 500 mW, 10X objective, acquisition time 2 sec), equiped with a 900 nm long-pass filter.

D) Evaluation of potential toxicity and reverse cycle of incubation of Daphnia with

6T@BNNTs, DPP3@BNNTs and BNNTs:

In order to evaluate the potential toxicity of our samples (6T, 6T@BNNTs, DPP2@BNNTs, DPP3@BNNTs and BNNTs), we kept 3 individuals of each group described in Table S1.

Daphniids were incubated for a period of 36 hours and there was no observed death of individuals, except from group B (incubated with free 6T at 5 µg/mL) who died after a few minutes of incubation, and group C (with 6T@BNNT at 100 µg/mL) who died after 20 hours of incubation due to aggregation of the probe in the digestive system. Next, to evaluate the capacity of daphniids to get rid of the 6T@BNNTs, DPP2@BNNTs and BNNTs after the 36h incubation experiment, we took living individuals of groups A, C, D, E and of Control 2 and transferred them to clean algae-free FLAMES (for 2 hours) followed by FLAMES/algae S2 and are described as follows:

-The Luminescence images and photobleaching experiments presented in Figure 3 were performed at 532 nm using the Raman/PL mapping system RIMA TM from Photon etc. In the Luminescence mode imaging the signal on the map is the integrated intensity of the

Figure 1 :

 1 Figure 1: Photoluminescence properties of 6T@BNNTs, DPP2@BNNTs and DPP3@BNNTs.

Figure 2 :

 2 Figure 2: Photostability and chemical resistance of 6T@BNNTs. a, Integrated luminescence

  provides distinct responses in the empty and filled regions (open circles 1 and 2, respectively), which are presented in Figs 3c-e. While the boron K-edge from the shell structure of BNNT at 192 eV is, as expected, measured in both regions 1 and 2, a new contribution is detected only in region 1 at the energy corresponding to the L2,3-edge of the sulfur atoms of 6T molecules. Local energy loss measurements in regions 1 and 2 (Fig. 3e) show the expected transitions at around 3 eV (region 1)

Figure 3 :

 3 Figure 3: Structural properties of a-sexithiophene (6T) encapsulated inside a double-walled

  photobleaching. In contrast, Daphniids incubated with PEG-Dyes@BNNTs (Fig.4a#3 -5) exhibit

Figure 4 :

 4 Figure 4: Dyes@BNNTs as hypermodal nanoprobes illustrated for Vis-NIR bio-imaging of

  Daphniids. Daphniids used in this work are Daphnia Pulex clones labeled DISP1312 -Disputed Pond in Ontario (coordinates: 42.17N, 83.03W), hence the DISP, and clone #1312. The culture medium, FLAMES, was prepared similarly to (2). DSPE-mPEG,(methoxy-poly(ethyleneglycol)-1,2-distearoyl-sn-glycero-3-phosphoethanolamine-N conjugates) (m.w. 5000) was purchased from Sigma-Aldrich. Adhesive glass slides were purchased from Surgipath Leica biosystems (model APEX Superior). Pre-cleaned white glass micro slides (25.5mm x 75.5 mm x 1mm) were used.

Figure S6 . 3 Characterization 3 . 1

 S6331 Figure S6. Photoluminescence of isolated DPP2@BNNT deposited on Si/SiO2 substrate as a

3. 2

 2 Characterization by Raman and photoluminescence. The Raman/PL measurements were taken from different set-up depending on the experiment. The equipment of the different set-ups is summarized in Table

-

  Photoluminescence (norm)

3. 3

 3 Characterization by HR-TEM and TEM-EELS TEM and high-angle annular dark-field (HAADF) STEM images in Figure 1 and S2a-b were recorded with a Libra 200 MC Zeiss operating at 200 kV and at 80 kV. The microscope is equipped with a monochromatic S.13Schottky FEG source delivering an energy resolution down to 150 meV and a Gatan Ultrascan camera. Point resolution is 2.3 Å and information limit is 1.2 Å at 200kV. The TEM can operate in scanning mode (STEM) and is equipped with Bright Field (BF) and HAADF detectors. The instrument is also equipped with an in-column energy filter making possible energy filtered TEM (EFTEM), EELS measurements in Scanning TEM mode and acquisition of spectrum imaging datacubes (or hyperspectral EELS). The STEM-HAADF probe size is about 2.5 nm (FigureS7).

Figure S7: a

 a Figure S7: a TEM and STEM-HAADF (left and right respectively) images at 80kV of a

Table S1 :

 S1 Description of the groups of Daphniids created for this study by type of sample used for the incubation

	Group of Daphniids	Group of materials dispersed in algae-free FLAMES, in which Daphniids were incubated	Concentration (µg/mL)	Main observations
				Individuals studied at
	A	BNNT dispersed in mPEG-DSPE	5; 25; 50; 100	concentrations 5 to 100 µg/mL
				were viable
	*B	free 6T	5	Death of daphniids in a few minutes
				Individuals studied at
				concentrations 5 to 50 µg/mL
				were viable. Individuals treated
	**C	6T@BNNTs dispersed in mPEG-DSPE	5; 25; 50; 100	with 100 µg/mL had probes aggregation in the digestive
				system, observed by optical
				microscope, dying after 20
				hours.
	D	DPP2@BNNTs dispersed in mPEG-DSPE	5; 25; 50	Individuals studied at concentrations 5 to 50 µg/mL were viable
				Individuals studied at
				concentrations 5 and 25 µg/mL
				were viable. Individuals treated
				with 50 µg/mL had some probes
	E	DPP3@BNNTs dispersed in mPEG-DSPE	5; 25; 50	aggregation in the digestive system, observed by optical
				microscope, but when
				transferred to algae-free
				FLAMES, the daphniids
				recovered completely.
		algae-free FLAMES used to
	Control 1	observe any inherent photoluminescence of Daphnia in	-	Death by starvation after 3-5 days
		the conditions of our study
	Control 2	mPEG-DSPE in algae-free FLAMES	5; 25; 50	Individuals were viable
		algae-free FLAMES to observe the
	Control 3	maximum period during which the individuals would resist before	-	Death by starvation after 3-5 days
		death by starvation

* The concentration of 6T was limited to 5 ug/mL due the low capacity of dispersion of the dye in the FLAMES.

Table S2 .

 S2 Raman/PL measurements setup used for the experiments

	Set up	Excitation	Objective	Dispersive	Detection
				element
	Custom optical	Verdi 532 nm	Olympus 50X	Grating, 600	CCD JY
	bench	HeNe 633 nm	long working	and 1800 tt/mm	nitrogen cooled
			distance NA
			0.55
	RIMA	Opus 532 nm	Olympus 100X	no	CCD Pixis
				(broadband	(Princeton Inst.)
				mode) optical	Peltier
				filters
	Renishaw InVia	Cobolt 473nm	Olympus 50X	Grating, 1200	CCD Renishaw
	Reflex			and 2400 tt/mm	RemCam,
					Peltier
	Fluorescence	U-RFL-T	10 X	no	UBG, TRITC
	microscope	mercury light			and TXRED
		source			filters

Acknowledgments

This work received financial support from the Natural Sciences and Engineering Research Council of Canada (NSERC), the Canada Research Chairs (CRC) programs. CA, RN, PD and RM acknowledge support from the consortium industriel de recherche et d'innovation en technology médicales du Québec (MEDTEQ) in collaboration with our partners Photon Etc. and La fondation du cancer du sein du Québec. No 706476 and Graphene Flagship Core 1 (No. 604391). EG acknowledges funding from the Marie-Skłodowska-Curie-IF 706476-BrightPhoton, the GDRi Graphene and Co and the GDRi multifunctional nano for travel support. The authors warmly acknowledge G. WANG for support on the Cs-corrected TEM of MPQ -Paris Diderot University and the METSA support for the access to the Cs-corrected TEM of MPQ. The authors would like to thank Cristescu's team (McGill University) for providing Daphniids, culture medium (FLAMES), algae and technical assistance, and help from L. Gaboury, J. Hinsinger and the Platform of Histology at Institut de Recherche en Immunologie et en Cancerologie (IRIC). The authors acknowledge BNNT LLC for providing raw BNNTs.

Authors Contributions

Competing Interest Statement

The authors declare no competing financial interests.

Supplementary information file for:

Photostable Fluorescence Imaging Using Dye Nanohybrids

Charlotte Allard 1 , Rafaella Nascimento 2 Frédéric Fossard 3 , Léonard Schué 2 , Emmanuel

Encapsulation of 6T and DPPx into BNNTs deposited on Si/SiO 2 substrates.

The sample was treated with concentrated nitric acid for 5 min and then baked at 800°C under vacuum to remove water. The sample was then immediately used for encapsulation. The substrate covered with BNNTs was gently placed into a flask equipped with a condenser and the solution was refluxed overnight at 115 °C (6T) or 80°C (DPPX). Following the encapsulation step, the sample was rinsed in fresh toluene, then IPA, and finally dried in N 2 .

Encapsulation of 6T into BNNTs on TEM grid (Mo/SiO 2 )

5 mg of raw powder of BNNTs was first mechanically grinded then dispersed into 15 ml of DMF using an ultrasonic bath for one hour. About 20 μL of this solution was drop-casted on a Molybdenum grid with holed SiO 2 membrane. The deposited BNNTs were then annealed at 350°C under atmospheric conditions, followed by another anneal under vacuum at 800°C during two hours. The grid was inserted in the 6T encapsulation solution at 115°C during 6 hours. Following the encapsulation, the grid was rinsed for a few seconds in DMF, cleaned using an oxygen plasma (100W, 10 minutes) and a piranha treatment (2 minutes) to completely remove the excess of non-encapsulated dyes.

Photobleaching experiments of 6T@BNNTs and DPP2@BNNTs

BNNTs were first deposited on Si/SiO2 substrates then encapsulated with 6T or DPP2 molecules using the protocol described in section 2.6. Then the integrated intensity of tracked isolated Dyes@BNNT was recorded using the hyperspectral Raman/luminescence imager RIMA TM from Photon etc. at an excitation wavelength of 532 nm. The time acquisition is 0.2 sec and the laser fluence is 1.2 µW.µm -2 .

Incubation of Daphnia Pulex with 6T@BNNTs and DPP3@BNNTs.

Why Daphnia ? Daphnia is a freshwater crustacean and one of the most studied subjects in Biology, including a fully sequence of its genome, a well-understood life cycle and its ecology. Daphniids are keystone organisms for environmental toxicity studies because they are considered as primary consumer in aquatic food chains (4). In our study, we chose Daphnia because they are filter feeders that conduct small suspended particles into their mouth by the current created by the motion of their leaf-like legs, which makes Daphnia an ideal candidate for our study on BNNTs or dyes@BNNTs suspended in the culture medium of daphniids (FLAMES). Furthermore, in optimal environmental conditions, daphniids reproduce by cyclical parthenogenesis, by generation of diploid eggs that develop directly into larvae at the female brood chamber. The parthenogenesis entails clonal reproduction. The sexual reproduction of daphniids is trigged by environmental stress (e.g. crowding, cooling, changes of photoperiod), which was avoided in our study. Moreover, we used only individuals which did not present any eggs or resting eggs or any larvae in the brood chamber. Furthermore, the maximum incubation time of daphniids with our samples (BNNTs, DPPx@BNNTs, 6T@BNNTs) was 12 hours, which is not enough to affect the reproduction cycle of 3 days. Daphnia is an ideal system to study the PL from dyes@BNNTs because of its feeding and reproduction systems, which allows us to have identical individuals in the laboratory.

Experiments with dyes@BNNTs in Daphnia.

A) Preparation of 6T, 6T@BNNTs, DPPx@BNNTs and BNNTs in FLAMES:

For interaction with Daphniids, BNNTs and dye@BNNTs were filtrated and rinsed in FLAMES at least 3 times. 1 mg of each sample was then dispersed in a solution of 200 µM mPEG-DSPE in FLAMES, adapted from a previous report (3), and diluted as needed. B) Incubation of 6T, 6T@BNNTs and DPPx@ BNNTs with Daphnia Pulex: Adult individuals of Daphnia Pulex (clones DISP1312) were kept at 22°C in FLAMES with algae for 4 days before the experiment, allowing a new reproducing cycle. Then, the specimens were transferred to a FLAMES medium algae-free and remained there for 1 day at minimum to clean the digestive system and limit any PL from algae during the images/time lapse acquisition -See Figure S3.

Photobleaching experiments on dye@BNNT assemblies

The stability of the dye@BNNT was assessed in solution, and compared to the dye alone, after an overnight exposition to a conventional lamp -see Figure (3) V. H. Lee, D. Zhang, Y. K. Yap, Functionalization, dispersion and cutting of boron nitride in water, J. Phys. Chem. C, 116, 1798-1804 (2012) (4) A. Siciliano, R. Gesuele, G. Pagano, M. Guida, How Daphnia (cladocera) assays may be used as bioindicators of health effects? J. Biodivers Endanger Species, 1, 5 (2015) download file view on ChemRxiv Supp for Mol@BNNT .pdf (3.54 MiB)


Karine Charriere

Audrey Guitton
email: audrey.guitton@u-psud.fr

Vanessa Ratié
email: vanessa.ratie@efs.sante.fr

Lydia Dumoulin
email: lydia.sighidumoulin@efs.sante.fr

Véronique Bourcier

Pascal Morel
email: pascal.morel@efs.sante.fr

Lionel Pazart
email: lpazart@chu-besancon.fr

Bruno Wacogne
email: bruno.wacogne@univ-fcomte.fr

K Charrière

L Sighi-Dumoulin

BLOOD-TO-BLOOD IMMUNOLOGICAL COMPATIBILITY TEST: A possibility with fluorescent immuno-biochips

Keywords: Crossmatch, human red blood cells, fluorescence, biochip, immuno-detection

whether they are published or not. The documents may come

INTRODUCTION

In France every year, more than 3 million labile blood products, 80% of which were red blood cells (RBC), are given to more than 550 000 patients [START_REF] Ansm | Rapport d'activité hémovigilance[END_REF]. French health institutions have seen a rise in deliveries of RBC of + 26.3% in total between 2000and 2014[START_REF] Efs | Rapport d'activité 2013[END_REF]. In 2016, according to the haemovigilance report by ANSM (National Agency for Drug Safety), 6780 adverse effects in recipients (AER) related to transfusion were reported. In total, 255 adverse effects in receivers related to transfusion were recorded due to immunological incompatibility. The situation seems to be similar in countries with the same level of safety as France.

In most countries, a crossmatch (a compatibility test between blood for transfusion and the receiver's blood) is carried out in a laboratory prior to transfusion. The current techniques for carrying out a crossmatch are either manual, with blood reagents and samples being mixed in tubes or being placed on gel columns before centrifuging, or automated. As far as these automated systems are concerned, the analyzers may only be used in a laboratory and the analyses are time consuming which can delays the delivery of the blood product. This test is even avoided in some emergency situations.

Currently, the final pre-transfusion test at the patient's bedside consists mainly of an identity check (identity of the red cell concentrate (RCC) and identity of the patient). This method cannot guarantee that there will be no transfusion accident because 50% of the reported adverse effects are due to human error, most of them being "wrong blood in tube" (SHOT 2011). Therefore, in spite of increasingly effective safety systems, it is currently impossible to eliminate entirely the risks due to human error, both in the laboratory and at the time of the transfusion. These errors highlight the need for a pre-transfusion analyzer which does not require pre-treatment (plasma extraction, and/or centrifugation) in order to limit human manipulation and subsequent errors.

Some research was carried out in order to make this process ultimately safe. They are mainly based on gel agglutination techniques which requires plasma extraction [START_REF] Cid | Comparison of three microtube column agglutination systems for antibody screening: DG Gel, DiaMed-ID and Ortho BioVue[END_REF]Longston et al. 1999) or SPR [START_REF] Malomgre | Recent and future trends in blood group typing[END_REF]Quinn et al. 2000;[START_REF] Houngkamhang | ABO Blood-Typing Using an Antibody Array Technique Based on Surface Plasmon Resonance Imaging[END_REF]. More recently, Long-Range Surface Plasmon-Polaritons have been suggested to detect selectively captured red blood cells using specific surface chemistry [START_REF] Krupin | Selective capture of human red blood cells based on blood group using long-range surface plasmon waveguides[END_REF]. This system can capture red blood cells in a sample with a very low cell concentration. The initial dilution of the sample is carried out in a buffer with a controlled refractive index. Blood samples must then be prepared which is not an improvement compared to current crossmatch. Test plates and image processing have also been proposed for phenotyping blood groups [START_REF] Ferraz | Automatic Determination of Human Blood Types using Image Processing Techniques[END_REF]. Micro fluidics coupled with optical fibers are reported in (Ramasubramanian et al. 2009). A while ago, we proposed the use of functionalized biochips for ABO and rhesus compatibility tests [START_REF] Charrière | Biochip technology applied to an automated ABO compatibility test at the patient bedside[END_REF][START_REF] Wacogne | Medical devices development: the bottom-up or the top-down approach?[END_REF].

Except the gel agglutination method which requires samples preparation, the other techniques could allow for blood grouping but not a direct compatibility check between the RCC to be transfused and the patient. The idea developed in this position paper arose from the fact that incompatible antibodies present in the patient's blood bind to red cells to be transfused and may lead, more or less rapidly, to the lyses of RCC.

Therefore, our proposal is to use a single biochip onto which red cells to be transfused are trapped. Subsequently, patient's whole blood is applied onto the biochip and possibly present irregular antibodies react with the RCC. Finally, fluorescent anti-IgGs antibodies are used in order to allow rapid optical detection. Using such an architecture allows detecting any erythrocytic immunological incompatibilities without extracting patient's plasma. In this way, this very rapid test can be performed by nonspecifically trained people, with a reduced and non prepared receiver's blood sample. This principle will be described in part 2 of this communication together with the actual biological model used to demonstrate a first proof of concept. A description of the experimental set-up and results obtained using fluorescence spectroscopy will be the subject of part 3. In part 4 and in line with the scope of a position paper, we will comment on the state of industrial competition and the new devices market positioning.

GENERAL PRINCIPLE AND ACTUAL IMMUNOLOGICAL MODEL

Biochip principle

The method we propose is depicted in figure 1 in the case of non-compatible transfusion. Red cells from the RCC to be transfused are applied to the biochip previously grafted with antibodies directed to a highincidence antigen (figure 1(a)). After rinsing, a RCC layer is formed at the biochip surface.

Figure 1: Principle of the blood-to-blood immunological compatibility test biochip.

Patient's whole blood is directly injected onto this surface (figure 1(b)). Antigen/antibody reactions occur when RCC exhibit an antigen which is complementary of an antibody present in the patient's blood (irregular IgGs in this case). After rinsing, elements which have not reacted with the red cells layer are evacuated.

Then, a solution of fluorescent anti-IgGs antibodies is applied to the biochip (figure 1(c)). These antibodies react with the patient's irregular antibodies forming a fluorescent layer at the biochip's surface. The latter is eventually detected using conventional fluorescence techniques.

In this example, irregular IgGs have been considered. However, incompatibility may be due to presence of IgM in the patient's whole blood (case of the ABO incompatibility). In this case, and this is not shown in this proof of concept communication, fluorescent anti IgMs antibodies should be employed. In order to address any incompatibility situation, the ideal sensor should be adapted to the presence of both IgGs and IgMs. A way of doing would be to use a mixture of fluorescent IgGs and IgMs antibodies. The fluorescent labels could be chosen in such a way that both exhibit the same excitation wavelength but different emission spectra. Here, a simple fluorescence spectrum fitting would furthermore indicate which kind of immuno-incompatibility arose.

Immunological model

In this model, RCC are captured on the biochip by means of anti Kell IgMs (figure 2). The KEL:2 antigen (cellano) is present at the red cell surface of about 99.6% of the population. Therefore, for this proof of concept, the anti Kell IgMs are considered universal. In the future, we will have to find a red cell capture method which also works for the remaining 0.4% of the population. In this example, red cells are Lub positive and Jka negative. For the positive test, a solution of irregular anti-Lub IgG antibodies is applied to the RCC immobilized on the biochip. In the same manner, a solution of anti-Jka antibodies is used for the negative test. When antigen-antibody reactions occur, antibodies bind to the red cells surface.

After rinsing, FITC coupled anti-IgGs antibodies are applied to the biochips. They react with the irregular antibodies possibly present at the RCC surface. In a positive test, a large amount of FITC coupled antibodies is present and a strong fluorescence signal is detected. On the contrary in a negative test, only non-specific interactions occur leading to a weak fluorescence signal.

For these experiments, commercially available irregular antibodies were used (Bio-Rad). Further experiments will be conducted with whole blood.

EXPERIMENTAL SET-UP AND PRELIMINARY RESULTS

Biochemical reactions

Immunological reactions described in figure 2 were performed using the fluidic system of our SPRi apparatus (SPRi-Plex imager, Horiba Scientific) at 37°C with a MLB2 (Bio-Rad) running buffer.

Biochips were prepared according to the process described in (Charriere et al. 2015) without RSA saturation. Anti-Kell IgMs (dilution 1/10 in acetate buffer, 10 mM and pH 4.5) were grafted onto biochips. 200 µL of pouch's red cells were injected onto the biochips at 20 µL/min. After rinsing, 200 µL, irregular antibodies (anti-Lub and anti-Jka, 1/10 in MLB2, BioRad) were injected at 20 µL/min. FITC anti-IgGs (Sigma) were injected (200 µL, 20µL/min, 1/25 in MLB2).

Complex red cells / antibodies were finally fixed using a 0.5% glutaraldehyde solution. Biochips were wetted with MLB2 buffer and protected with cover slits before fluorescence measurements.

Fluorescence measurement set-up

FITC was excited at 488 nm using an Oxxius 488-50-COL-PP laser. Excitation light was injected into a fluorescence beam-splitter as shown in figure 3.

This beam-splitter (Doric Lenses) is equipped with excitation and emission filters together with a dichroic mirror (respectively FF01-488/10-25, BLP01-488R-25 and FF500-Di01-2536). Fluorescence spectra were recorded using a QE-Pro spectrometer (Ocean Optics).

Additional fluorescence

This kind of beam-splitter is usually designed to be used with optical fibres. Because we use it in an open beam configuration, additional fluorescence signals are observed due to multiple reflexions in the beamsplitter (figure 4). This additional fluorescence is mainly generated by the epoxy resin used to glue optical elements in the beam-splitter. The shape of the additional fluorescence was recorded and used as explained in the next section.

Experimental results

Overall, 18 measurements were performed with 2 demonstration biochips (7 random places on the positive biochip and 11 on the negative). Fluorescence spectra were recorded as above mentioned. In order to isolate the contribution of the FITC signal from the whole recorded spectrum a simple fitting was employed. Indeed, we recorded the shape of the additional fluorescence and we know the shape of the FITC emission spectrum. Fitting the experimental spectra with these 2 shapes allows separating the contribution of the FITC from the contribution of the additional fluorescence. Figure 5(a) shows an example of spectrum recorded with the positive biochip.

In this figure, the green shape corresponds to the FITC while the grey shape correspond to the additional fluorescence. It can be seen that the fitting efficiently reproduces the recorded spectra. The feature reported on the right of the spectra represents the standard deviation of the difference between the experimental spectrum and the fitted one. It is an estimation of the fitting accuracy. It is clearly observed that the signal due to the FITC (about 10000 levels) is much greater than the signal of the additional fluorescence.

In figure 5(b), we present a spectrum obtained with the negative biochip. Here the shape of the additional fluorescence is clearly visible. As previously mentioned, 18 spectra were recorded. Table 1 summarizes the levels of FITC and additional fluorescence obtained at each places of the biochips. From these data, it can be seen that the level of additional fluorescence is relatively constant (700±50 levels). Also, FITC levels of the positive biochip is always much larger (except for the QEP003631_17 spectrum). It is however possible to define a threshold above which a biochip is considered positive. This is shown in figure 7 where a threshold at 1300 levels is reported. This figure shows that the experimental set-up can be drastically simplified as a simple photodiode can be used to detect positive biochips. This would make the final device cost-effective and would ensure its use in a large number of situations.

Figure 8: Extracting a weak FITC response using spectral fitting.

However, the use of fluorescence spectroscopy may prove to be extremely useful in the case of weak antigen-antibody affinity or weak concentration of irregular antibodies. In some cases indeed, even a very low antibody concentration can lead to severe consequences for the patient (for example the anti-Jka). The interest of fluorescence spectroscopy is illustrated in figure 8 which reproduces results obtained with the QEP003631_20 spectrum. This demonstrates that a simple fitting can extract a weak level of FITC signal from a spectrum possibly recognized as negative. Importantly, it must be noted that figure 8 does not represent a weak affinity/avidity situation but a case of non-specific interaction at the place where the spectrum was recorded.

To conclude this experimental section, this work represents the preliminary results demonstrating that the immuno-biochip technology can be used to perform a complete blood compatibility test without plasma extraction. Further experiments are still required with a large range of irregular antibodies before considering a clinical trial on a larger scale.

MARKET POSITIONING

In countries with a safe transfusion system (80% of wealthy countries and 60% of averagely wealthy countries), the compatibility check is carried out either in the laboratory or at the patient's bedside, or both in some cases.

In the laboratory, ABO grouping of RCC and the patient are carried out by analysers (Bio-Rad, Diagast, HTZ, Dia Pro, Grifols). The current techniques for carrying out a crossmatch or an irregular antibody screening are either manual, with blood reagents and samples being mixed in tubes or being placed on gel columns before centrifuging (e.g. Across Gel® Cross Match, from Dia Pro or ID-Card 50531 from Bio-Rad), or automated (e.g. the Qwalys analysers from Diagast). The analysers require additional time-consuming manual operations, (blood centrifugation for example) which may increase the risk of errors. Furthermore, they are oversized for technical platforms or small size laboratories.

To mitigate these risks, some countries, including France, have formalised a final ABO compatibility check at the patient's bedside (ABO compatibility charts from Bio-Rad, Diagast). This check requires qualified and regularly trained staff, is limited to ABO compatibility and cannot prevent certain human errors in terms of allocation, realization or interpretation.

During the work presented here, a market research carried out by a specialist firm and companies with a potential interest, found that the biochip technology, is of major interest. There is nothing similar in this enormous market. This market research also showed that the final control of just ABO compatibility on a biochip would not currently be sufficient to penetrate the world market because of the practices in place in most countries. The companies we approached strongly advised increasing the added value of this biochip by broadening its application to carry out crossmatch, what we did. Given this international perspective, the two initial patents we published (Pazart et al. 2001(Pazart et al. -1, 2011-2) -2) were also broadened and recorded in Europe, North America and in "BRIC" countries.

We have presented the proof of concept of a biochip potentially able to perform a blood-to-blood immunological compatibility test in a simple fluidic environment. It relies on a single biochip onto which red cells to be transfused are trapped. Subsequently, patient's whole blood is applied onto the biochip and possibly present incompatible antibodies react with the RCC. Eventually, fluorescent anti-IgGs antibodies are used in order to allow rapid optical detection.

Fluorescence spectroscopy experiments showed that irregular antibodies can easily be detected. Here, we used solutions of irregular antibodies. The next steps will consist in multiplying the types of irregular antibodies and to perform experiments with whole blood obtained from donors. Potentially, a simple photodiode based detection can be used. This would allow using a compact device which can be used either by trained or non trained medical staff. However, the use of fluorescence spectroscopy in a more complex set-up can probably lead to the detection of weak but potentially dangerous incompatibilities.

Figure 2 :

 2 Figure 2: Immunological model used in this proof of concept.

Figure 3 :

 3 Figure 3: Fluorescence beam-splitter used in these experiments.

Figure 4 :

 4 Figure 4: Origin of the additional fluorescence.

Figure 5 :

 5 Figure 5: Fluorescence spectra of: (a) positive biochip, (b) negative biochip.

Figure 7 :

 7 Figure 7: Definition of a positive threshold.

Table 1 :

 1 Summary of the fluorescence levels obtained with the 18 measurements on 2 biochips (1 positive, 1 negative).

	Type	Spectra N°	FITC	Add.	std
		QEP003631_11	12525	757	0.61
		QEP003631_12	7470	766	0.39
	Positive	QEP003631_13 QEP003631_14 QEP003631_15	8419 11261 12355	702 797 732	0.64 0.37 0.58
		QEP003631_16	13935	702	0.7
		QEP003631_17	1784	575	2.27
		QEP003631_02	0	666	1.79
		QEP003631_03	0	697	1.72
		QEP003631_04	198	697	1.31
	Negative	QEP003631_05 QEP003631_06 QEP003631_20 QEP003631_21	198 270 577 537	697 657 672 668	1.31 1.78 1.15 1.51
		QEP003631_22	8	664	1.65
		QEP003631_23	24	663	1.78
		QEP003631_24	6	732	1.73
		QEP003631_25	74	750	2.06

ACKNOWLEDGMENTS

This work is funded by the Etablissement Français du Sang Bourgogne Franche-Comté, contract "X-ult", April 2015.