Olivier Gauwin

Joachim Niehren

Sophie Tison

Earliest Query Answering for Deterministic Nested Word Automata

Earliest query answering (eqa) is an objective of streaming algorithms for XML query answering, that aim for close to optimal memory management. In this paper, we show that eqa is infeasible even for a small fragment of XPath unless P=NP. We then present an eqa algorithm for queries and schemas defined by deterministic nested word automata (dnwas) and distinguish a large class of dnwas for which streaming query answering is feasible in polynomial space and time.

Outline. In Sec. 2, we show how to define queries for unranked trees. In Sec. 3 we recall nested word automata. In Sec. 4, we present hardness results for sufficiency problems. In Sec. 5, we show how to decide sufficiency for queries defined by dnwas incrementally, in order to obtain an eqa algorithm in Sec. 6.

Appendix A recalls results on the expressiveness and efficiency of nwas.

Introduction

Streaming algorithms process input streams in an incremental manner, and write their output to some external output collection. The data content on the input stream may be huge, so that only fragments of bounded size can be memorized in main memory at every time point. Furthermore, the input stream is usually restricted to a single reading pass (see [START_REF] Grohe | Tight lower bounds for query processing on streaming and external memory data[END_REF][START_REF] Schweikardt | Machine models and lower bounds for query processing[END_REF] for more general models).

Streaming algorithms for XML input data streams that contain XML documents, i.e., linearizations of unranked trees or equivalently nested words. In this paper, we are mainly interested in streaming query answering for node selection queries in XML documents, which return collections of tuples of nodes. Such queries may be defined in the W3C standard language XPath 2.0, whose core has the same expressiveness as first-order logic for unranked trees, or by tree automata. The domain of queries can be restricted by schemas defined by the W3C standard XML Schema or again by tree automata.

For illustration, let us simplify XML documents into words with alphabet {a, b}, and consider the monadic query Q 0 that selects all b positions succeeded by aa in words of {a, b} * . This query can be defined by the first-order formula lab b (x) ∧ lab a (x + 1) ∧ lab a (x + 2) with one free variable x. Its answer set on word t 0 = abbaabaaba is Q 0 (t 0 ) = {3, 6}. A streaming algorithm for query Q 0 reads some word t ∈ {a, b} * from the input stream and computes Q 0 (t) incrementally. The first answer candidate encountered is letter b at position 2. Whether it will be selected or not depends on the continuation of the stream, and thus position 2 must be stored by all streaming algorithms. We call such answer candidates alive. The next event is letter b at position 3. Good streaming algorithms reject candidate 2 now and discard it from memory. In turn, position 3 becomes alive and must be stored. It can be safely selected from position 5 on, written to the external output collection, and discarded from internal memory.

We need a notion of streamability that accounts for both space and time. We call a class E of query definitions streamable, if there exists a polynomial p and an algorithm mapping query definitions e ∈ E to streaming algorithms A e in time p(|e|), such that A e computes the answer set of query Q e for all trees t on the input stream, with space and time per step bounded by p(|e|) independently of t. Bar-Yossef et al. [START_REF] Bar-Yossef | Buffering in query evaluation over XML streams[END_REF] showed for a class of XPath queries, that the maximal number of simultaneous alive answer candidates (for all positions of the input stream) is indeed a lower space bound for every streaming query answering algorithm. This number is called the concurrency concur Q (t) of a query Q for an unranked tree t. Classes of queries with unbounded concurrency are thus not streamable. Few positive streamability results exist. Boolean queries (returning true or false) defined by tree automata with languages of trees of bounded depth are streamable [START_REF] Segoufin | Validating streaming XML documents[END_REF][START_REF] Segoufin | Constant-memory validation of streaming XML documents against DTDs[END_REF]. Simply compute all runs in parallel on the fly with a stack of bounded depth. A streaming algorithm with close to optimal memory management for Boolean queries defined in a small fragment of positive Forward XPath was presented in [START_REF] Bar-Yossef | On the memory requirements of xpath evaluation over xml streams[END_REF]. Benedikt et al. [START_REF] Benedikt | Stream firewalling of XML constraints[END_REF] showed P-time streamability for the fragment of Boolean Core XPath 1.0 queries in shallow trees, that never look forwards. Heuristics are proposed to approximate earliest rejection. Streamability results for monadic queries are lacking so far.

Earliest query answering (eqa) is the objective of many recent approaches that hint for streaming algorithms with polynomial time and space [START_REF] Bar-Yossef | Buffering in query evaluation over XML streams[END_REF][START_REF] Olteanu | SPEX: Streamed and progressive evaluation of XPath[END_REF][START_REF] Berlea | Online evaluation of regular tree queries[END_REF][START_REF] Benedikt | Efficient and expressive tree filters[END_REF][START_REF] Kumar | Visibly pushdown automata for streaming XML[END_REF]. The strategy is to memorize alive answer candidates only, in order to reach close to optimal memory management. eqa trades space for time: all eqa algorithms need to decide at every step, whether the current answer candidates are safe for selection or rejection (otherwise they are alive). We call these two decision problems sufficiency for selection resp. rejection. Benedikt et al. [START_REF] Benedikt | Stream firewalling of XML constraints[END_REF] noticed (Theorem 1) that rejection sufficiency for Boolean XPath queries that never look forwards is pspace-hard.

As a first contribution, we present hardness results for selection sufficiency. For arbitrary classes of query definitions, we show how to reduce selection sufficiency to a language inclusion problem. As a corollary, we obtain coNP-hardness of selection sufficiency for a small fragment of Forward XPath filters with only child and descendant axis (without schemas) by reduction to universality of Boolean queries [START_REF] Miklau | Containment and equivalence for a fragment of XPath[END_REF]. Thus, the P-time streaming algorithms in [START_REF] Olteanu | SPEX: Streamed and progressive evaluation of XPath[END_REF][START_REF] Gou | Efficient algorithms for evaluating XPath over streams[END_REF] cannot be earliest, except if P=NP. This result shows that [START_REF] Olteanu | SPEX: Streamed and progressive evaluation of XPath[END_REF] does not fully reach its progressiveness objective, and furthermore it contradicts Theorem 3 of [START_REF] Gou | Efficient algorithms for evaluating XPath over streams[END_REF] on optimal memory management (without proof). As a counter example, consider the Forward XPath expression //a[not[child::c] and [child::b]], which queries for a-nodes without c-children but with a b-child. Both algorithms will keep a-nodes in memory even when encountering a c-child (and remove them only after closing the last child).

As a second contribution, we provide an eqa algorithm for n-ary queries defined by deterministic nested word automata (dnwas) [START_REF] Alur | Adding nesting structure to words[END_REF][START_REF] Alur | Visibly pushdown languages[END_REF]. Our result relies on new automata constructions deciding selection and rejection sufficiency in an incremental manner. Without determinism, we show that selection sufficiency for Boolean nwas is exptime-complete by reduction to universality of tree automata [START_REF] Seidl | Haskell overloading is DEXPTIME-complete[END_REF]. Let Q e be queries with fixed arity n ≥ 0 that are defined by a pair of dnwas e = (A, B) which recognizes the canonical language and the domain (aka schema) of the query respectively, and let t ∈ L(B) be a tree satisfying the schema on the input stream. Our eqa algorithm for e computes Q e (t) with the following costs, where d = depth(t) is the depth of the tree and c = concur Qe (t) the concurrency of the query on the tree:

-polynomial precomputation time in O(|A| 3 • |B| 3 ); -polynomial space for all steps in O(c • d • |A| • |B|); -polynomial time for all steps in O(c • |A| 2 • |B| 2 ).
As a corollary, a subclass E of queries defined by dnwas is streamable, if depth and concurrency are bounded by some polynomial p such that d = depth(t) ≤ p(|B|) and c = concur Qe (t) ≤ p(|A| • |B|) for all e = (A, B) ∈ E and t ∈ L(B). Related work. Preliminary versions of this paper were presented at the workshops Plan-X'08 and AutoMathA'09. Independently, we showed in [START_REF] Gauwin | Bounded delay and concurrency for earliest query answering[END_REF] how to decide bounded concurrency for queries defined by dnwas in P-time, by reduction to bounded valuedness of recognizable tree relations.

Schemas defined by dnwas subsume extended deterministic DTDs with restrained competition [START_REF] Martens | Which XML schemas admit 1-pass preorder typing?[END_REF] modulo a P-time transformation. Kumar, Madhusudan and Viswanathan [START_REF] Kumar | Visibly pushdown automata for streaming XML[END_REF] investigate eqa by dnwas, but for a restricted class of monadic queries which always allow for immediate node selection at opening time. Similarly, Benedikt and Jeffrey [START_REF] Benedikt | Efficient and expressive tree filters[END_REF] consider immediate node selection at opening and closing time, for XPath filters on depth-bounded documents. Madhusudan and Viswanathan [START_REF] Madhusudan | Query automata for nested words[END_REF] propose a streaming algorithm for monadic queries defined by nwas. They impose a serious restriction on their automata so that the sufficiency becomes trivially decidable in P-time. This class of automata is not proved to be complete for MSO, and the cost of the translation to this class is not investigated. Our results answer to these questions.

nwas are equivalent modulo P-time to pushdown forest automata [START_REF] Neumann | Locating matches of tree patterns in forests[END_REF][START_REF] Berlea | Online evaluation of regular tree queries[END_REF][START_REF] Gauwin | Streaming tree automata[END_REF]]. Berlea's [START_REF] Berlea | Online evaluation of regular tree queries[END_REF] P-time eqa algorithm for queries defined by a variant of pushdown forest automata is very different to ours in that no determinism is assumed. This works out, since he assumes infinite signatures so that universality and sufficiency become trivially decidable, in contrast to a finite signature, where sufficiency becomes exptime-hard. With infinite signature, however, schemas can no more be expressed, closure under complement fails, and MSO is no more captured (in contrast to what is stated in Section 3.1 of [START_REF] Berlea | Online evaluation of regular tree queries[END_REF]). Thus, while eqa becomes much simpler, it looses much of its interest.

Bar-Yossef et al. [START_REF] Bar-Yossef | Buffering in query evaluation over XML streams[END_REF] proposed a streaming algorithm with optimal memory management for monadic queries in shallow trees defined in a fragment of Forward XPath queries. Unfortunately, this algorithm is incorrect since it doesn't try to decide rejection sufficiency. Whether this problem might be solvable by adding further restrictions is open.

Σ

were m ≥ 0. Nodes of trees and hedges are words over natural numbers defined by nod (a(t 1 , . . . , t m )) = {ǫ} ∪ nod ((t 1 , . . . , t m )) and nod

((t 1 , . . . , t m )) = ∪ m i=1 {i•π | π ∈ nod (t i )}.
We denote the label of node π ∈ nod (t) by lab t (π) ∈ Σ. The empty word ǫ is the root of all trees (but of no hedge). The word π•i ∈ nod (t) is the ith child of π. Let child t ⊆ nod (t) 2 be the father-child relation and lab t a = {π | lab t (π) = a} the labeling relation for a ∈ Σ.

Linearizations of unranked trees in pre-order are called nested words in [START_REF] Alur | Visibly pushdown languages[END_REF][START_REF] Alur | Adding nesting structure to words[END_REF]. We write nw(t) for the nested word of t. For instance

, if t = a(b, c(d), f ) then nw(t) = (op, a)•(op, b)•(cl, b)•(op, c)•(op, d)•(cl, d)•(cl, c)•(op, f )•(cl, f )•(cl, a).
In XML syntax, an opening tag (op, a) is written as < a > and a closing tag (cl, a) is written as < /a >. We ignore data values throughout this paper. We consider streaming algorithms receiving nested words nw(t) on the input stream. The positions of nw(t) can be identified with the following set of events:

eve(t) = {start} ∪ ({op, cl} × nod (t))
If lab t (π) = a then event (op, π) specifies an occurrence of opening tag < a > in an XML stream, and event (cl, π) the corresponding occurrence of closing tag < /a >. Fig. 1(c) illustrates a nested word with edges of relating corresponding events, established by some parser in parallel preprocessing. Let ≺ t be the total order on eve(t), i.e., the order of the tags in the XML stream, and for every e except start let pr (e) be the immediate predecessor of e in that order. For hedges, events are defined by: eve

(h) = {start} ∪ ({op, cl} × nod (h)).
A schema is a tree language S ⊆ T Σ . An n-ary query is a function Q with schema S is a function Q with domain dom(Q) = S that selects a set of n-tuples of nodes Q(t) ⊆ nod (t) n for every tree t ∈ S. Boolean queries are queries of arity n = 0. The canonical language of an n-ary query Q is a set of annotated trees L Q ⊆ T Σ×B n , where B = {0, 1} are the Booleans. For all trees t ∈ dom(Q) and tuples ν ∈ nod (t) n , we define an annotated tree t ′ = t * ν in T Σ×B n that has the same structure as t, i.e., nod (t ′ ) = nod (t), while annotating the node labels of t by bit vectors, such that lab t ′ (π) = (lab t (π), β) for all nodes π ∈ nod (t), where

β = (b 1 , . . . , b n ), ν = (π 1 , . . . , π n ) and b i = 1 ⇔ π = π i for all 1 ≤ i ≤ n.
The canonical language of an n-ary query Q is the set of all annotated trees for Q, i.e.:

L Q = {t * ν | ν ∈ q(t)}. For Boolean queries, L Q ⊆ dom(Q).
Queries Q (A,B) in unranked trees can be defined by a pair (A, B) of automata with languages

L(A) = L Q and L(B) = dom(Q (A,B) ). If L(B) = T Σ then we write Q A for Q (A,B) .

Nested Word Automata

In the present paper, we consider nwas [START_REF] Alur | Adding nesting structure to words[END_REF] as automata operating directly on unranked trees (as proposed in [START_REF] Gauwin | Streaming tree automata[END_REF] and similarly to pushdown forest automata [START_REF] Neumann | Locating matches of tree patterns in forests[END_REF][START_REF] Berlea | Online evaluation of regular tree queries[END_REF]) whereas they usually operate on linearizations of unranked trees nw(t) or slightly more general nested words.

An nwa A = (Σ, Γ, stat, init, fin, rul ) consists of a finite signature Σ of node labels, a finite set stat with subsets init, fin ⊆ stat of initial and final states, a finite set Γ of stack symbols, and a set rul ⊆ {op, cl} × Σ × Γ × stat 2 of rules. We denote rules as:

p 0 α a:γ ---→ p 1
where α ∈ {op, cl}, p 0 , p 1 ∈ stat, a ∈ Σ, γ ∈ Γ . Whenever necessary, we will upper index components of A, as for instance, writing rul A instead of rul . An nwa traverses the sequence of events of a given tree t, while annotating all events of t by states and all nodes of t by stack symbols. Let p 0 be the state of the previous event processed, and (α, π) be the current event. The automaton chooses some rule with action α and label a = lab t (π) whose left hand side is p 0 . If α = op then it annotates node π with stack symbol γ. If α = cl then the rule matches only, if the stack symbol annotated at opening time to π is equal to the stack symbol γ of the rule. For matching rules, the automaton annotates state p 1 on the right hand side to the current event.

More formally, a run of an nwa on a tree t is a function r with two types r : eve(t) → stat and r : nod (t) → Γ which maps events to states and nodes to stack symbols, such that r (start) ∈ init and the following rule belongs to rul for all π ∈ nod (t) with a = lab t (π), and actions α ∈ {op, cl}. r (pr (α, π))

α a:r (π) -----→ r ((α, π))
An example of a run of an nwa on the tree a(a, a(a, a(b), b))) is given in Fig. 1. It tests whether this tree satisfies the Boolean XPath query [//a[child::b]], or equivalently the first-order formula ∃x(lab a (x) ∧ ∃y(child(x, y) ∧ lab b (y))). When opening an a-node in its initial state 0, this nwa guesses whether it matches the a-position of the XPath expression (state 1) or not (state 0). From state 1, it waits while traversing a sequence of states (2 * 1) * , until some b-child is opened, before concluding success in state 3. The information of being a child of the a-node opened in state 1 is annotated by stack symbol y, and passed over from the left to the right. A run r of A on a tree t is successful if r ((cl, ǫ)) ∈ fin A . The set of all possible runs of the nwa A on the tree t is denoted runs A (t) and the subset of all successful runs by runs succ A (t). The recognized language L(A) is the set of all trees t ∈ T Σ that permit a successful run by A, i.e., L(A) = {t ∈ T Σ | runs succ A (t) = ∅}. For a hedge (t 1 , . . . , t k ), a run is successful if r (start) ∈ init A and r ((cl, k)) ∈ fin A .

An nwa is deterministic or a d nwa , if it has a single initial state, no two op rules for the same letter use the same state on the left, and no two cl rules for the same letter use the same stack symbol and the same state on the left. The unique run of a dnwa A on a tree t can be computed in a streaming manner, if it exists. The input is the nested word nw(t) of some t that is enriched by the nesting relation by parallel preprocessing with a SAX parser, and the output is the sequence of states that A assigns to the events of t. In order to do so, A has to be stored, and at every time point the current state and the stack of symbols that are annotated to the nodes on the path from the root to the current node. The maximal memory needed at any time point is O(|A| + depth(t) + 1).

Complexity of Earliest Query Answering

We present the decision problems of eqa algorithms for n-ary node selection queries and establish lower complexity bounds.

We have to define sufficient events for tuple selection. For every η ∈ eve(t) -{start}, let the tree prefix t η be the fragment of t which contains all nodes of t opened before or at event η. Note that t (cl,π) contains all proper descendants of π in t, while t (op,π) does not. For two trees t, t ′ ∈ T Σ and η ∈ eve(t) we define equal η (t, t ′ ) by η ∈ eve(t) ∩ eve(t ′ ) and t η = t ′ η , i.e., t and t ′ have the same prefix until η. Definition 1. (Sufficient events for selection) Let Q be an n-ary query over Σ and t ∈ dom(Q) a tree. We relate tuples ν ∈ nod(t) n to events η ∈ eve(t) that are sufficient for their selection:

(ν, η) ∈ sel Q (t) ⇔ (ν ∈ nod(t η ) n ∧ ∀t ′ ∈ dom(Q). equal η (t, t ′ ) ⇒ ν ∈ Q(t ′ )) Note that (ν, η) ∈ sel Q (t) implies ν ∈ Q(t)
. Furthermore, successors of sufficient events are sufficient. Consider for instance the monadic query Q 1 with schema T {a,b,c} defined by the XPath expression //a[child::c]/child::b, or equivalently by the first-order formula lab b (x)∧∃y (lab a (y)∧child(y, x)∧∃z(child(y, z)∧lab c (z))) with one free variable x. On tree t = b(a, a(a, b, c)), the earliest time point to select node 2•2 is event (op, 2•3) when the c-child is opened, i.e., ((2•2), (op, 2•3)) ∈ sel Q1 (t). For query Q 2 defined by the same XPath expression, but with a more restrictive schema, requiring that all inner a-nodes have at least one c-child, we can select node 2•2 at opening time, i.e.,

((2•2), (op, 2•2)) ∈ sel Q2 (t).
For optimal memory management, it is equally important to discard rejected answer candidates in an earliest manner, i.e., candidates that will never be selected in any possible future. Going one step further, one might also want to remove rejected partial candidates, for which no completion will ever be selected in any future. Partial candidates ν are elements of nod ⊘ (t η ) n = (nod (t η )⊎{⊘}) n , the symbol ⊘ denoting components where no selection occurred so far. Completions compl (ν, t, η) are complete candidates obtained by replacing ⊘-components of ν by nodes of t opened after η. Definition 2. (Sufficient events for rejection) We call a candidate ν rejected at event η, or equivalently η sufficient for failing ν, if no completion of ν can be selected in the future:

(ν, η) ∈ rej Q (t) ⇔ ν ∈ nod ⊘ (t η ) n ∧ ∀t ′ ∈ dom(Q). equal η (t, t ′ ) ⇒ ∀ν ′ ∈ compl(ν, t ′ , η). ν ′ / ∈ Q(t ′ )
We call a candidate ν alive at event η, if η is not sufficient for selection or rejection of ν, i.e., (ν, η) / ∈ sel Q (t) ∪ rej Q (t). eqa algorithms store only alive candidates. The maximal number of alive candidates at a same event is called concurrency [START_REF] Bar-Yossef | Buffering in query evaluation over XML streams[END_REF], and written concur Q (t). For sake of clarity, however, we have to omit the study of rejection sufficiency in the core of the paper (see the appendix).

sufficiency has to be decided for all candidates by all eqa algorithms at every event. selection sufficiency for a class of query definitions E is the problem that receives as input a definition e ∈ E of a query Q e with arity n, a tree t ∈ T Σ , an event η ∈ eve(t), and a tuple ν ∈ nod (t) n , and sends as output the truth value of (ν, η) ∈ sel Q (t). We provide hardness results selection sufficiency for some query classes E. Proofs and further details, including schemas considerations, are provided in Appendix B.

First, we consider Boolean queries defined by XPath filters F in the following fragment. All trees satisfy the label constraint * , while only trees a(. . .) satisfy the label constraint a. A filter [child::ℓ F ] is satisfied by all trees with a subtree at a child position of the root that satisfies ℓ and F . A filter [//ℓ F ] is satisfied by trees having a subtree satisfying ℓ and F . We freely omit filter [true] in examples.

F ::= [child::ℓ F ] | [//ℓ F ] | [F 1 and F 2 ] | [not F ] | [true] for ℓ ∈ Σ ∪ { * } Proposition 1.
sufficiency for Boolean queries defined in the above fragment of XPath is coNP-hard, even without schema assumptions.

As a consequence, every eqa algorithm for a larger fragment of xpath cannot be in polynomial time, except if P=NP.

Second, we study this problem for queries defined by automata. For nondeterministic ones, sufficiency remains hard, even with Boolean queries. Proposition 2. sufficiency for Boolean nwa queries is exptime-hard.

However, when restricted to deterministic nwas, the problem becomes tractable.

Theorem 1. sufficiency for n-ary d nwa queries is in polynomial time.

This justifies the use of dnwas in the following, and shows that sufficiency is exptime-complete for nwas (by using nwa determinization).

Inferring Safe States

For dnwa queries, we propose a method for deciding sufficiency at each event of a tree. Our solution is based on a new dnwa construction. Given a dnwa A for the query, we build a dnwa E(A) that accepts the same language, and contains enough information in its states to decide for selection sufficiency at each event immediately. For clarity, sufficiency for rejection is presented in Appendix C, and schemas are discussed at the end of Section 6.

We define a partial run r of an nwa A on a tree t like a run, except that it operates only on a prefix t η for some event η ∈ eve(t). We write p runs A (t) for the set of all partial runs of A on t. Let A be a dnwa over Σ × B n defining a query Q A , t ∈ T Σ , η ∈ eve(t), and ν ∈ nod (t) n . We call a state p ∈ stat A safe for selection of ν at event η if the existence of a partial run r of A on t that maps η to p implies (ν, η) ∈ sel QA (t). In other terms, these are the states that ensure sufficiency for selection when they are reached.

safe sel A (ν,η) (t) = {p | (∃r ∈ p runs A (t * ν) ∧ r (η) = p) ⇒ (ν, η) ∈ sel QA (t)} p0 op a:γ 1 ----→ p1 ∈ rul A S1 = univ sel A (a, γ1, S0) (p0, S0) op a:(γ 1 ,S 0 ) --------→ (p1, S1) ∈ rul E(A) p0 cl a:γ 0 ----→ p1 ∈ rul A S0, S1 ⊆ stat A (p0, S0) cl a:(γ 0 ,S 1 ) --------→ (p1, S1) ∈ rul E(A) init E(A) = (init A , fin A ) fin E(A) = {(p, fin A ) | p ∈ fin A } Fig. 2. Construction of E(A) from A a h p 0 γ p 2 p 1
The remainder of this section describes how these states can be computed by a new dnwa E(A), which permits to decide sufficiency. Here we need some auxiliary definitions. Let runs A p0→p1 (h) be the set of runs of an nwa A on a hedge h that start in state p 0 and end in state p 1 . The operator ev cl A (h, p 0 , a, γ) evaluates hedge h from state p 0 and subsequently applies a closing rule with label a and state γ:

ev cl A (h, p 0 , a, γ) = {p 2 | ∃r ∈ runs A p0→p1 (h). p 1 cl a:γ ----→ p 2 ∈ rul A }
We consider continuations through hedges in H sel = T * Σ×{0} n . The operator univ sel A (a, γ, P ) computes all states, from where all hedges in H sel can be evaluated and closed wrt a and γ into a state of P ⊆ stat A :

univ sel A (a, γ, P ) = {p 0 | ∀h ∈ H sel . ev cl A (h, p 0 , a, γ) ∩ P = ∅}
Given A, t, and ν, we can compute inductively the safe states S sel (η) = safe sel A (ν,η) (t) for all events η ∈ eve(t). First, for the closing event of the root, the set of safe states for selection are the final states: S sel ((cl, ǫ)) = fin A . Second, at each node π, the safe states for opening events can be computed from those of the corresponding closing event:

S sel ((op, π)) = univ sel A (a, γ, S sel ((cl, π)))
where a = lab t (π) and γ = r A (π). Third, the safe states for the opening event of π are equal to those for the closing events of children of π, i.e., S sel ((op, π)) = S sel ((cl, π•i)).

These propagation rules allow to infer safe sel A (ν,η) (t) for all events η. This can be done by running the nwa E(A) defined in Fig. 2, which adds safe states to each state of A. The signature of E(A) is Σ × B n as for A. The state sets may be exponentially large, since stat

E(A) = stat A × 2 stat A and Γ E(A) = Γ A × 2 stat A .
Stack symbols are used to pass safe states from parents to all their children. Proposition 3. Let A be a d nwa on Σ × B n that defines a query, and t * ν ∈ T Σ×B n . Then E(A) is a d nwa that accepts the same language as A. Furthermore, if r A (resp. r E(A) ) is the unique run of A (resp. E(A)) on t * ν then r A detailed proof is in Appendix C. 4 Running automaton E(A) for a candidate permits to test sufficiency for selection at the event when it happens. At most one run has to be processed per candidate, thanks to determinism.

E(A) (η) = (r A (η), safe sel A (ν,η) (t)) for all η ∈ eve(η) -{start}. a ∈ Σ × {0} n p1 op a:γ ----→ p3 ∈ rul A p4 cl a:γ ----→ p2 ∈ rul A accH sel (p1, p2) :-accH sel (p3, p4). p ∈ stat A accH sel (p, p). p1, p2, p3 ∈ stat A accH sel (p1, p2) :-accH sel (p1, p3),accH sel (p3, p2).

EQA Algorithm for dNWAs

We present an eqa algorithm for queries defined by dnwas A which runs in polynomial time per step. The idea is to run the earliest automaton E(A) of Section 5 on the input stream in order to decide selection sufficiency for all answer candidates at all time points, without constructing E(A) explicitly, since it may be of exponential size compared to A. Recall that deciding rejection sufficiency is needed for all eqa algorithms too. This is explained in the appendix.

Running E(A) on the Fly. Given a dnwa A over Σ × B n and a tree t * ν over the same signature, we want to compute a run of E(A) on t * ν in polynomial time in the size of A. The application of closing rules of E(A) is easy, since it only has to look for a rule of A. Applying opening rules of E(A) is a little more tedious, since we have to compute the set univ sel(a, γ, P ) while given a ∈ Σ, γ ∈ Γ A , and P ⊆ stat A .

When assuming the completeness of A beside of determinism (which can be ensured in polynomial time), these sets can be computed by reduction to information on accessibility through hedges for A. Given a set H ⊆ T * Σ×B n of hedges, and states p 1 , p 2 ∈ stat A , we define the following accessibility predicate: To explain the computation of univ sel A , we introduce befClose A (a, γ, P ), the set of states that lead to a state of P after closing a with γ: Lemma 1. For complete d nwas A, the safe states univ sel A (a, γ, P ) are:

acc A H (p 1 , p 2 ) ⇔ ∃h ∈ H. runs A p1→p2 (h) = ∅ We compute it for H sel = T * Σ×{0} n ,
befClose A (a, γ, P ) = {p 0 | ∃p 1 ∈ P. p 0 cl a:γ ----→ p 1 ∈ rul A } f u n answer ( e ,
{p | acc A H sel (p, p 0 ) ⇒ p 0 ∈ befClose A (a, γ, P )}
Generic Algorithm. Our algorithm will be obtained by instantiating the skeleton in Fig. 4 of a generic eqa algorithm, which is parameterized by a class E of query definitions. The static input of the algorithm is a query definition e ∈ E, and its dynamic input on the stream is a nested word nw(t). We assume that the nested word is parsed by some parallel preprocessor. Our algorithm can thus process the stream of events of t while knowing their matching relation. It then adds the tuples of Q(t) to the external output collection incrementally at the earliest possible event. The main idea is to generate all candidate tuples, test their aliveness repeatedly, output selected candidates and remove rejected candidates.

Instantiation for d nwas 5 . Now suppose that the query is defined by a dnwa A. For every candidate ν we maintain its current state (p, S) ∈ stat E(A) and a sequence Υ ∈ (Γ E(A) ) * that we call stack, whose length is the depth of the current node of t. Sufficiency for selection (ν, η) ∈ sel Q (t) holds iff p ∈ S.

Updating the current set of candidates at event η means to apply a rule of E(A) to the current state (p, S) ∈ E(A), and for opening events to create all new candidates, where the current node is used. More precisely, for generating these candidates, we can restrict to the ones generated by continuations of the runs of old candidates. Thus, the number of candidates to process at an event is bounded by c + i, where c = concur Q (t) is the concurrency of the query Q, and i = immediate Q (t) is the number of new candidates that immediately get safe for selection or rejection. We have seen already how to apply rules of E(A) in polynomial time in the size of A. The node state of the rule is pushed to stack Υ for opening events, and popped from Υ for closing events. Adding Schemas. With respect to sufficiency checking, we can integrate the schema into the query. Validation of the document with respect to the schema is an independent task, that we run in parallel. Given an n-ary query Q and a schema S, define a query Q S sel with domain T Σ :

Q S sel (t) = Q(t) if t ∈ S, and nod (t) n otherwise
It is easy to check that sel Q = sel Q S sel so that we can test sufficiency for selection as before. The necessary dnwa constructions are in Appendix E. The overall costs of the resulting eqa algorithm with schemas have already been reported in the introduction.

Conclusion.

We distinguished a large class of streamable query-schema definitions defined by dnwas. This class was obtained by designing an eqa algorithm in a first step and bounding the concurrency of the query and the depth of trees in a second. We have shown that eqa is infeasible for nondeterministic nwas if n ≥ 1, as well as for Forward XPath with child and descendant axis. In subsequent work [START_REF] Gauwin | Streaming Tree Automata and XPath[END_REF], we have shown that these classes are indeed not streamable, and distinguished schema restricted fragments of Forward XPath, that can be proven to be streamable by P-time compilation into dnwas. This proves that the notion of determinism of dnwas is essential for streamability. An open question is whether we can extend our eqa algorithm to deterministic pushdown automata.

A Nested Word Automata

We clarify basic expressiveness and efficiency questions for dnwas and nwas by comparison to standard tree automata.

We start with the expressiveness of dnwas and nwa compared to monadic second-order (MSO) logic. The following variant of Thatcher and Wright's theorem can be found for instance in [START_REF] Alur | Adding nesting structure to words[END_REF]. The main point is that dnwas are able to capture the bottom-up determinism of stepwise tree automata [START_REF] Carme | Querying unranked trees with stepwise tree automata[END_REF].

Theorem 3 (Alur & Madhusudan [START_REF] Alur | Adding nesting structure to words[END_REF]). nwas and d nwas capture MSOdefinable queries.

Proof. Stepwise tree automata can converted into nwas in linear time, such that determinism is preserved. When moving downwards, the nwa ignores all information seen. When moving upwards or left to right, is simulates the stepwise tree automaton. The downwards movement is clearly deterministic, and the other movements remains deterministic when simulating deterministic stepwise tree automata.

Vice versa, it is not difficult to convert nwas into stepwise tree automata. Which can be determinized into dnwas. This shows that nwas, dnwas, and stepwise tree automata recognize the same tree languages. The variant of Thatcher and Wright's theorem for unranked trees shows that a query Q is MSO-definable iff its canonical language L Q is recognizable by a (bottom-up) deterministic stepwise tree automaton, which is equivalent to Q being definable by a dnwa.

The polynomial time back-and-fourth translation between stepwise tree automata to nwas used in the above proof also shows that decision problems of nwas are equivalent modulo P-time reductions to the corresponding decision problems of standard tree automata on binary trees. Proposition 5. Language inclusion and universality are in P-time for dnwas but exptime-complete for nwas.

Proof. A exptime algorithm for universality can be obtained by complementation after determinization and completion, and then emptiness checking. Here, we present a direct proof for exptime-hardness for universality. Let S ⊆ T {a,b} be the set of binary trees where a has arity 2 and b arity 0, i.e., s ∈ S ::= a(s 1 , s 2 ) | b. A standard tree automaton B recognizing binary trees in S has rules of the form a(p 1 , p 2 ) → p and b → q where p, p 1 , p 2 ∈ stat(B). We define nwas A from tree automata B in linear time such that L(A) = L(B):

stat(A) = stat(B) ⊎ {ok} stat(A) = Γ (A) fin(A) = {ok} init(A) = fin(B) b → p ∈ rul (B) p op b:ǫ ---→ ok ∈ rul (A) ok cl b:ǫ ---→ ok ∈ rul (A) a(p 1 , p 2 ) → p ∈ rul (B) p op a:p2 ----→ p 1 ∈ rul (A) ok cl a:p2 ----→ p 2 ∈ rul (A)
Let C be an nwa that recognizes T {a,b} -S. An nwa for L(A) ∪ L(C) can be constructed in P-time from A. Now, we have L(B) = S if and only if L(A) ∪ L(C) = T {a,b} so that we can reduce universality of B to universality of A.

[child::

ℓ F ] t = {π | ∃π ′ ∈ F t. (π, π ′ ) ∈ child t , ℓ ∈ { * , lab t (π ′ )}} [//ℓ F ] t = {π | ∃π ′ ∈ F t. (π, π ′ ) ∈ (child t ) * , ℓ ∈ { * , lab t (π ′ )}} [F1 and F2] t = F1 t ∩ F2 t [not F ] t = nod (t) -F t [true] t = nod (t)

B Complexity of Earliest Query Answering

We study the complexity of selection sufficiency for various classes E of query definitions, whose expressions (A, B) ∈ E define a canonical language L(A) and and a schema L(B), and thus a query Q (A,B) of some arity n.

Selection sufficiency for E obtains as input a pair of (A, B) ∈ E, a tree t ∈ L(B), an event η ∈ eve(t), and a tuple ν ∈ nod (t) n , and returns as outputs the truth value of (ν, η) ∈ sel QA (t). Every eqa algorithm needs to solve the sufficiency problem, since a node is sufficient at an event if and only if it is the algorithms adds it to the output collection, before this event happens. Let S A,ν,η,t be the set of trees on which ν is selected or that have a prefix different from

t η . S A,ν,η,t = {t ′ ∈ T Σ | equal η (t, t ′ ) ⇒ ν ∈ Q A (t ′ )} Lemma 2. (ν, η) ∈ sel Q (A,B) (t) ⇔ ν ∈ nod(t η ) n ∧ L(B) ⊆ S A,ν,η,t .
This reformulation of the definition of sel QA,B (t) relates sufficiency to language inclusion for classes of Boolean queries. This inclusion problem for a class E of Boolean queries inputs an pair (A, B) ∈ E and outputs the truth value of L(B) ⊆ L QA = L(A) since Q A is Boolean. universality returns the truth value of T Σ ⊆ L(A) instead.

Lemma 3. (Hardness) For all classes E of definitions of Boolean queries there is a linear time reduction of inclusion to sufficiency, and of universality to sufficiency for queries with schema T Σ .

Proof. Let (A, B) ∈ E and t ∈ L(B) a tree. Since Q A is Boolean, the definition yield S A,(),start,t = L(A). Thus, Lemma 2 proves that ((), start) ∈ sel QA,B (t) if and only if L(B) ⊆ L(A).

We consider Boolean filters in the fragment of Forward XPath mentioned in the core of the paper, where ℓ ∈ Σ ∪ { * }:

F ::= [child::ℓ F ] | [//ℓ F ] | [F 1 and F 2 ] | [not F ] | [true]
Whether a filter expression is satisfied at the root of a tree t, in formulas ǫ ∈ F t , is recalled in Fig. 5. Proposition 6. sufficiency for Boolean queries defined in the above fragment of Forward XPath is coNP-hard, even without schema assumptions.

Proof. According to Hardness Lemma 3, sufficiency without schemas is harder than universality of Boolean queries. Since Descending XPath provides negation and disjunction in filters, inclusion is indeed equivalent to universality. This holds, since

T Σ ⊆ L [[not F 1 ] or F 2 ] iff L F1 ⊆ L F2 .
In turn, inclusion for Boolean queries in the above fragment of Forward XPath (even without negation and disjunction) was proven coNP-hard by Miklau and Suciu [START_REF] Miklau | Containment and equivalence for a fragment of XPath[END_REF].

Proof. The Boolean operations for dnwas are in P-time, and emptiness checking too. For possibly non-deterministic nwas, we can encode universality of unrestricted stepwise tree automata, which is exptime-hard, since these can be identified with standard tree automata. Proposition 7. sufficiency for Boolean nwa queries is exptime-hard, even without schema assumptions.

Proof. By Lemma 3, sufficiency without schemas is harder than universality for nwas, and thus exptime-hard by Proposition 5.

Lemma 4. If a d nwa A defines a query, we can compute a d nwa recognizing language S A,ν,η,t in P-time.

The crucial point here is that dnwas can check the equality of the prefixes of two trees until event η deterministically.

Proof. We prove that we can build a dnwa recognizing S A,ν,η,t in polynomial time from A, t, π ∈ nod (t), α ∈ {op, cl}, and ν ∈ nod (t) n . We define two tree languages:

Eq t,η = {t ′ | equal η (t, t ′ )} Q ν = {t ′ | ν ∈ Q A (t ′ )}
With these definitions, we get S QA,ν,η,t = Eq compl t,η

∪ Q ν where L compl = {t ∈ T Σ | t /
∈ L} for L ⊆ T Σ . Hence it suffices to build dnwas recognizing Eq t,η and Q ν in P-time.

First of all, we define a dnwa recognizing Eq t,η = {t ′ | equal η (t, t ′ )}. We set stat = eve(t η ), Γ = {γ} (arbitrary), init = {start}, fin = {η}, and the following rules where and pr are interpreted on eve(t):

(α, π) η a = lab t (π) pr ((α, π)) α a:γ ---→ (α, π) a ∈ Σ η op a:γ ----→ η η cl a:γ ----→ η
Second, we define a dnwa recognizing the set

Q ν = {t ′ | ν ∈ Q A (t ′ )}.
Such a dnwa can be built in several steps. We first build a dnwa A ′ recognizing all trees annotated with the tuple ν, i.e.:

L(A ′ ) = {t * ν | t ∈ T Σ }
Then we can intersect A ′ with A, in order to distinguish all annotated trees on which ν is selected by Q A . Finally, we can project on the Σ-component in order to obtain the desired trees:

Q ν = Π Σ (Q A ∧ Q A ′ ) (a, 0, 0) (b, 0, 1) (c, 0, 0) (d, 0, 0) (e, 1, 0) (f, 0, 0) ǫ 1 ǫ ⊥ ⊥ 1 2 ⊥ ⊥ ⊥ 2•1 2 ⊥ ⊥ 2•1 ⊥ ⊥ ⊥ ⊥
Fig. 6. A run of the dnwa A ′ , when ν = (2•1, 1). The domain for this ν is domain = {ǫ, 1, 2, 2•1}, as indicated by framed nodes.

The corresponding automata operations preserve determinism, in this particular case: for each tree t ∈ T Σ , there is at most one run of A ∩ A ′ on t * ν, as both automata are deterministic. Hence, after projection, there is also at most one run on t, and thus the determinism is preserved by the projection, in this case. It remains to detail the construction of A ′ . If the arity of Q A is n = 0 then ν = () and we can take a universal automaton, as L(A ′ ) = T Σ . Otherwise, in order to define this automaton in polynomial size in |ν|, some preprocessing on ν is required, which factorizes common prefixes of node addresses. Roughly speaking, we call domain the domain of the smallest tree containing ν, and build a dnwa that computes in its states the next element of domain to be checked, as illustrated in Fig. 6. Formally, let domain be the set of positions π smaller or equal to some position of ν for the order defined by π.i < π.j if i < j and π < π.i. We write domain ⊥ = domain ∪ {⊥}. We introduce the function next: {op, cl} × (N * ∪ {⊥}) → domain ⊥ that indicates whether the domain still continues above (resp. at the right of) the current node π, when called with (op, π) (resp. (cl, π)):

   next(op, π) = π•1 if π•1 ∈ domain, ⊥ otherwise next(cl, π•i) = π•(i + 1) if π•(i + 1) ∈ domain, ⊥ otherwise next(α, ⊥) = ⊥ for α ∈ {op, cl}
We also introduce the function vars ν : domain ⊥ → B n that associates with each node the variables corresponding to the annotation by ν:

vars (π1,...,πn) (π) = (b 1 , . . . , b n ) where b i = 1 if π i = π 0 otherwise
We can now define the dnwa A ′ . A run of A ′ is shown in Fig. 6.

stat A ′ = Γ A ′ = domain ⊥ init A ′ = ǫ fin A ′ = {⊥} a ∈ Σ π, π ′ ∈ domain ⊥ l = vars ν (π) π op (a,l):π ------→ next(op, π) ∈ rul A ′ π ′ cl (a,l):π ------→ next(cl, π) ∈ rul A ′ p0 op a:γ 1 ----→ p1 ∈ rul A S1 = univ sel A (a, γ1, S0) R1 = univ rej A (a, γ1, R0) (p0, S0, R0) op a:(γ 1 ,S 0 ,R 0 ) ----------→ (p1, S1, R1) ∈ rul E ′ (A) p0 cl a:γ 0 ----→ p1 ∈ rul A S0, S1, R0, R1 ⊆ stat A (p0, S0, R0) cl a:(γ 0 ,S 1 ,R 1 ) ----------→ (p1, S1, R1) ∈ rul E ′ (A) init E ′ (A) = (init A , fin A , stat A -fin A ) fin E ′ (A) = {(p, fin A , stat A -fin A ) | p ∈ fin A } Fig. 7. Construction of E ′ (A) from A
Theorem 4. sufficiency for d nwas queries and schemas is in polynomial time.

Proof. We can test L(B) ⊆ S A,ν,η,t in polynomial time, if B is given an dnwa, since we can compute a dnwa for S A,ν,η,t in linear time by Lemma 4, and since inclusion for dnwas is in polynomial time (Proposition 5).

As a corollary sufficiency for nwas is exptime-complete. A exptime algorithm follows from nwa determinization and Theorem 4. By Proposition 7, the lower bound holds already for nwas defining Boolean queries.

C Inferring Safe States

We provide and prove a complete construction, that takes also into account failure states.

The treatment of safe states for rejection is more delicate. Here we have to assume determinism and need a new argument for a proper treatment of partial candidates. The definitions safe rej , univ rej and S rej remain the same, except that we have to replace sel by rej , ν ∈ nod (t) n by ν ∈ nod ⊘ (t) n , and H sel by H rej = T * Σ×B n . Rejection states at the root are precisely these states: S rej ((cl, ǫ)) = stat Afin A . Propagation rules remain unchanged too, but correctness requires two new arguments. The critical rule S rej ((op, π)) = univ rej A (a, γ, S rej ((cl, π))) remains correct when imposing determinism and completeness on A, since this ensures that a hedge will fail iff a run on this hedge leads to a rejection state. The additional quantification over hedges in H rej (in the definition of univ rej), which may turn continuations into non-canonically annotated trees, doesn't harm, since such trees cannot be recognized by A, when assuming that the language of A is canonical (it defines a query), as we do.

Now the propagation rules allow to infer both safe sel A (ν,η) (t) and safe rej A (ν,η) (t) for all events η. This can be done by running the nwa E ′ (A) defined in Fig. 7. The signature of E ′ (A) is still Σ × B n , as for A. The state sets may also be exponentially large, since stat

E ′ (A) = stat A × 2 stat A × 2 stat A and Γ (E ′ (A)) = Γ (A) × 2 stat A × 2 stat A .
Note that E ′ preserves determinism. Proposition 8 below subsumes Proposition 3. Proposition 8. Let A be a d nwa on Σ × B n that defines a query, and t * ν ∈ T Σ×B n . Then E ′ (A) is a d nwa that accepts the same language as A.

Furthermore, if r A (resp. r E ′ (A) ) is the unique run of A (resp. E ′ (A)) on t * ν then for all η ∈ eve(η) -{start}:

r E ′ (A) (η) = (r A (η), safe sel A (ν,η) (t), safe rej A (ν,η) (t))
Proof. We prove this proposition by Lemmas 5 and 6. For the whole section, we fix A, a dnwa on Σ × B n that defines a query, t * ν ∈ T Σ×B n , and we suppose that r A is the unique run of A on t.

Let us consider the function f that associates a pair (S, R) ∈ 2 stat A × 2 stat A to each event of t * ν (except start) using the following inference rules:

f ((cl, ǫ)) = (fin A , stat A -fin A ) (1) π ∈ nod (t) f ((cl, π)) = (S, R) a = lab t (π) γ = r A (π) f ((op, π)) = (univ sel A (a, γ, S), univ rej A (a, γ, R)) (2)
π ∈ nod (t) π•i ∈ nod (t) f ((op, π)) = (S, R) f ((cl, π•i)) = (S, R) (3)
Lemma 5. For every event η ∈ eve(t) -{start},

f (η) = (safe sel A (ν,η) (t), safe rej A (ν,η) (t))
Proof. We proceed by induction on events of t (except start), according to a top-down, breadth-first, right-to-left traversal of t.

For (cl, ǫ), the result is trivial from rule (1) and the definitions of safe sel and safe rej.

Let e = (op, π), and suppose that the property holds for (cl, π). From the application of rule (2), we know that f (η) = (univ sel A (a, γ, S), univ rej A (a, γ, R)) with f ((cl, π)) = (S, R), a = lab t (π) and γ = r A (π). By definition, we have: univ sel A (a, γ, S) = {p | ∀h ∈ H sel . ev cl A (h, p, a, γ) ∈ S}, and by induction hypothesis, S = safe sel A (ν,(cl,π)) (t). We first prove that univ sel A (a, γ, S) = safe sel A (ν,η) (t). Suppose that p ∈ safe sel A (ν,η) (t). Let h ∈ H sel , and p ′ = ev cl A (h, p, a, γ). Then p ′ ∈ safe sel A (ν,(cl,π)) (t), as sufficiency remains true for events following η. Thus, p ∈ univ sel A (a, γ, S). Conversely, if p ∈ univ sel A (a, γ, S) then ν ∈ nod (t η ) n (consider the empty continuation). So for every t ′ ∈ T Σ such that equal η (t, t ′ ), the hedge

h of children of π in t ′ is in H sel . Thus ev cl A (h, p, a, γ) ∈ safe sel A (ν,(cl,π)) (t), which means that ν ∈ Q A (t ′ ), so η is sufficient for selecting ν, and p ∈ safe sel A (ν,η) (t). Finally, univ sel A (a, γ, S) = safe sel A (ν,η) (t).
Now we prove the similar result for safe states for rejection, i.e., that:

univ rej A (a, γ, R) = safe rej A (ν,η) (t)
The difference here is that we deal with partial candidates. We write ν η for the partial tuple obtained by replacing every component strictly after η by ⊘. Inclusion safe rej A (ν,η) (t) ⊆ univ rej A (a, γ, S) holds for the same reason, namely events following η remain sufficient for failing, even for completions of ν η . Now suppose that p ∈ univ rej A (a, γ, S). Fix t ′ ∈ T Σ such that equal η (t, t ′ ), and let h be the hedge of children of π in t ′ . Then ev cl A (h, p, a, γ) ∈ safe rej A (ν,(cl,π)) (t), and thus every completion ν ′ of ν η after η fails. Hence η is sufficient for failing ν η , and p ∈ safe rej A (ν,η) (t). Finally we consider e = (cl, π•i), and assume that the property holds for (op, π) and (cl, π). From Rule (3) and induction hypothesis, we obtain that:

f ((cl, π•i)) = (safe sel A (ν,(op,π)) (t), safe rej A (ν,(op,π)) (t)). First we prove that safe sel A (ν,(op,π)) (t) = safe sel A (ν,η) (t). We have: p ∈ safe sel A (ν,(op,π)) (t) ⇔ (∃r ∈ p runs A (t * ν) ∧ r ((op, π)) = p) ⇒ (ν, (op, π)) ∈ sel QA (t) ⇔ (∃r ∈ p runs A (t * ν) ∧ r ((op, π)) = p) ⇒ ∀h ∈ H sel . ev cl A (h, p, a, γ) ∈ safe sel A (ν,(cl,π)) (t) ⇔ (∃r ∈ p runs A (t * ν) ∧ r ((cl, π•i)) = p) ⇒ (ν, (cl, π•i)) ∈ sel QA (t) ⇔ p ∈ safe sel A (ν,(cl,π•i)) (t) We now show that safe rej A (ν,(op,π)) (t) = safe rej A (ν,η) (t): p ∈ safe rej A (ν,(op,π)) (t) ⇔ (∃r ∈ p runs A (t * ν) ∧ r ((op, π)) = p) ⇒ (ν, (op, π)) ∈ rej QA (t) ⇔ (∃r ∈ p runs A (t * ν) ∧ r ((op, π)) = p) ⇒ ∀h ∈ H rej .ev cl A (h, p, a, γ) ∈ safe rej A (ν h ,(cl,π)) (t) ⇔ (∃r ∈ p runs A (t * ν) ∧ r ((cl, π•i)) = p) ⇒ (ν, (cl, π•i)) ∈ rej QA (t) ⇔ p ∈ safe rej A (ν,(cl,π•i)) (t)
where ν h is obtained from ν by adding annotations of h. Lemma 6. There is a run (r E ′ (A) , r E ′ (A) ) of E ′ (A) on t * ν, and for every event η ∈ eve(t) -{start},

r E ′ (A) (η) = (r A (η), S, R) with (S, R) = f (η)
Proof. Inference schemas defining E ′ (A) show that every run r of A has a unique corresponding run r ′ in E ′ (A), and r is the first component of r ′ .

Again, we use an induction on events of t (except start) according to a top-down, breadth-first, left-to-right traversal of t.

For e = (cl, ǫ), we have f (η) = (fin A , stat Afin A ). At the root, we have r (ǫ) = (r A (ǫ), fin A , stat A -fin A ) , so r ((cl, ǫ)) = (r A ((cl, ǫ)), fin A , stat A -fin A ). Now consider that e = (op, π) and suppose that we have r

E ′ (A) ((cl, π)) = (r A ((cl, π)), S ′ , R ′ ) with (S ′ , R ′ ) = f ((cl, π)). This implies that r E ′ (A) (π) = a ∈ Σ × B n p1 op a:γ ----→ p3 ∈ rul A p4 cl a:γ ----→ p2 ∈ rul A accH rej (p1, p2) :-accH rej (p3, p4). p ∈ stat A accH rej (p, p).
p1, p2, p3 ∈ stat A accH rej (p1, p2) :-accH rej (p1, p3),accH rej (p3, p2). Fig. 8. Inference rules for the definition of acc A H rej (r A (π), S ′ , R ′ ), so we get S ′ = univ sel A (a, γ, S), R ′ = univ rej A (a, γ, R) and r E ′ (A) (η) = (r A (η), S, R) where a = lab t (π) and γ = r A (π). Hence, (S, R) = f ((op, π)).

Finally, let us assume that e = (cl, π•i) and also that r E ′ (A) ((op, π)) = (r A ((op, π)), S, R) with S, R defined by (S, R) = f ((op, π)). By an immediate induction on children of π, each child π•j of π verifies r E ′ (A) (π•j) = (r A (π•j), S, R) and for the state r E ′ (A) ((cl, π•j)) = (r A ((cl, π•j)), S, R), and in particular for j = i. From rule (3) of the definition of f , we know that (S, R) = f ((cl, π•i)).

D EQA Algorithm for dNWAs

To build E ′ (A) on-the-fly, one need to compute univ rej(a, γ, P ) at each opening event. To do so, we use the accessibility relation acc A Hrej of A through hedges of H rej .

The following proposition subsumes Proposition 4. The following lemma subsumes Lemma 1.

Lemma 7. For deterministic and complete A, the safe states univ X A (a, γ, P ) are equal to:

{p | acc A HX (p, p 0 ) ⇒ p 0 ∈ befClose A (a, γ, P )}
Instantiation for d nwas. Here we have to maintain the current state (p, S, R) ∈ stat E ′ (A) and a sequence Υ ∈ (Γ E ′ (A) ) * . Sufficiency for selection (ν, e) ∈ sel Q (t) is verified by testing p ∈ S, and sufficiency for rejection (ν, e) ∈ rej Q (t) by checking p ∈ R. Updating the current state is done by applying a rule of E ′ (A), that we can compute using the alternative definition of univ X above. Proposition 2 (as recalled below) remains true when detection of rejection sufficiency is added. Here we use immediate(t, Q, S) to measure the number of new candidates for which sufficiency for selection or rejection can be decided immediately. For a tuple ν and a node π, we write νπ for the tuple obtained from ν by replacing π by ⊘.

immediate(t, Q, S) = max π∈nod(t) |{ν |    ν -π = ν ∧ ν -π is alive at event pr ((op, π)) ∧ ν
is not alive at event (op, π) Proof. Processing an opening event requires more computations than a closing one, as it needs to determine the sufficient events. Given a label a ∈ Σ and a current state (p 0 , S 0 , R 0 ) for the partial run of the candidate, there are at most 2 n rules of A c of the form p 0 op a β :γ1 -----→ p 1 . For each of these rules, the computation of befClose(a β , γ 1 , S 0 ) can be performed in time Proposition 4). Then, the computation of univ X where X ∈ {sel , rej } can be done in time

}| = max π∈nod(t) |{ν |    ν -π = ν ∧ (ν -π, pr ((op, π))) / ∈ sel S Q (t) ∪ rej S Q (t) ∧ ( ν , (op, π) ) ∈ sel S Q (t) ∪ rej S Q (t
O(|rul Ac |) = O(|Σ| • |stat A | 2 ) (see proof of
O(|stat A | 2 ).
Space consumption is due to the computation of sets of safe states and their storage inside the stack.

Implementation. We provide here a more precise and efficient procedure for the computation of safe states univ X where X ∈ {sel , rej } for a dnwa A. We first exhibit some properties of the function mapping sets P to befClose(a, γ, P ) and, where a and γ are fixed. Lemma 8. For every a ∈ Σ, γ ∈ Γ A , and P 1 , P 2 ⊆ stat A : befClose(a, γ, P 1 ∪ P 2 ) = befClose(a, γ, P 1 ) ∪ befClose(a, γ, P 2 ) So we get befClose(a, γ, P 2 ) = ∪ p∈P2 befClose(a, γ, {p}). Hence we can precompute befClose(a, γ, {p}) for each a ∈ Σ, γ ∈ Γ A and p ∈ stat A , and reuse it for computing befClose(a, γ, P 2 ). This precomputation requires time O(|Σ| • |A| 3 ) and space O(|Σ| • |A| 2 ). An alternative can be not to precompute, but to compute on-the-fly, and keep in memory the results. Now we look into more details the properties of the function mapping sets P to univ X (a, γ, P ) for fixed a and γ. Lemma 9. For every a ∈ Σ, γ ∈ Γ A , P 1 , P 2 ⊆ stat A and X ∈ {sel, rej}: univ X(a, γ, P 1 ∪ P 2 ) ⊇ univ X(a, γ, P 1 ) ∪ univ X(a, γ, P 2 ) A consequence is that the function mapping sets P → univ X (a, γ, P ) is monotonic. Note that in the general case, univ X (a, γ, P 1 ∪P 2 ) ⊆ univ X (a, γ, P 1 )∪ univ X (a, γ, P 2 ). A counter example will be given later on in Appendix F. There we have (0, 2) / ∈ univ rej(a 1 , 0, {(1, 2)}) and (0, 2) / ∈ univ rej(a 1 , 0, {(3, 2)}), but (0, 2) ∈ univ rej(a 1 , 0, {(1, 2), (3, 2)}). Algorithm of Fig. 9 uses these results, and also the fact that, from Lemma 7, univ X (a, γ, P 2 ) ⊆ befClose(a, γ, P 2 ). Note that if we choose to store all the computations of safe states (used in the first for loop), this can use memory of size O(|Σ|

• |Γ A | • |2 stat A | 2
). However, this can be weakened. For instance a good trade-off between memory and time consumption can be to store all safe states of all previous siblings of the current branch. The reason is that the safe states at opening are computed from the safe states at closing, which are the same for all siblings. Thus, if two siblings have the same label and the same associated stack symbols, their safe states are equal.

E Adding Schemas

In the core of the paper, we introduced the query Q S sel , that was used for computing selection sufficiency for both the query Q and schema S:

sel S Q = sel Q S sel .
As for selection, we can integrate the schema into the query such that detecting rejection on the query Q with schema S is equivalent to detecting rejection on the new query Q S rej . In other terms, rej S Q = rej Q S rej when Q S rej is defined by: For selection detection, the idea is to build an automaton B sel from the nwas A and B recognizing respectively the canonical language of Q and the schema S, where B sel is such that Q B sel = Q S sel . This automaton will be similar to the product automaton of A and B, but final states will be enriched by all invalid selections, as introduced in the definition of Q S sel . Fig. 10 shows how to obtain the nwa B sel . Prior to this construction, A and B must be determinized and completed. For failure detection, we proceed the same way to obtain B rej such that Q Brej = Q S rej . The only difference between B sel and B rej lies in the final states:

Q S rej (t) = Q(t) if t ∈ S, and ∅ otherwise p0 op a β :γ 1 -----→ p1 ∈ rul A p ′ 0 op a:γ ′ 1 ----→ p ′ 1 ∈ rul B (p0, p ′ 0 ) op a β :(γ 1 ,γ ′ 1 ) --------→ (p1, p ′ 1 ) ∈ rul B sel p0 cl a β :γ 0 -----→ p1 ∈ rul A p ′ 0 cl a:γ ′ 0 ----→ p ′ 1 ∈ rul B (p0, p ′ 0 ) cl a β :(γ 0 ,γ ′ 0 ) --------→ (p1, p ′ 1 ) ∈ rul B sel init B sel = init A × init B fin B sel = (fin A × fin B ) ∪ (stat A × (stat B -fin B ))
fin Brej = fin A × fin B .
This way, we can compute the safe states for selection with E ′ (B sel ) and the safe states for failure with E ′ (B rej ). From an implementation point of view, there is no need to compute the safe states for failure of E ′ (B sel ) and the safe states for selection of E ′ (B rej ). Thus, we can run the efficient algorithm presented in Section 6 and compute the same amount of safe states as for E ′ (A), but on a bigger automaton. A complete example is provided in Appendix F.

F Example Run of Algorithm with Schema

For illustration consider the monadic query Q 0 that selects all nodes without next sibling. It can be defined in MSO by the formula ¬∃y.ns(x, y). The root of t is selected, and this can be decided when opening it. Without schema, membership π ∈ Q 0 (t) cannot always be decided at opening time, so the algorithm needs to memorize nodes until, either encountering the opening event of the next sibling (for nodes π / ∈ Q 0 (t)) or the closing the father (for selected nodes π ∈ Q 0 (t)). When assuming the DTD a → (a * b) * and b → ǫ, one knows that all a-nodes except the root have a next sibling in all trees satisfying the DTD, so selection of a nodes be decided early at opening time. For b-nodes, selection can still be decided only later, when closing the parent.

We consider the schema S 0 which corresponds to the DTD {a → a * b, b → ǫ}. We show how the algorithm would behave on this input.

In the sequel, we write a β for the annotated node label (a, β) ∈ Σ × B n .

In the following figures, we omit stack symbols as only one occurs in each automaton. Moreover, whenever x occurs in a rule, this means that this rules exists for x ∈ {a, b}. Let A be the nwa represented in Fig. 11 In the following, we show how safe states are computed in the case with schema, as explained in Section 6 and Appendix E. We start by completing A with the sink state 3 and B with the sink state 2. By applying the inference rules of Fig. 10, we obtain the nwa B sel represented in Fig. 12 (states resulting from completion are omitted for clarity). The nwa B rej only differs on final states.

Then we compute the relations acc H sel and acc Hrej . Fig. 13 is an array of Booleans representing the relation acc Hrej . States (p 0 , p 1 ) are written p 0 p 1 for sake of conciseness. The relation acc H sel is obtained from this array by replacing values in italics by 0.

Suppose that we want to compute the safe states at the root for the labeling a 0 on our example. This corresponds to computing safe sel B sel (a 0 , γ, fin B sel ). First, we obtain from the "cl" rules of B sel : 0 1 1 0 0 1 0 0 1 0 0 1 02 0 0 1 0 0 1 0 0 1 0 0 1 10 0 0 0 1 0 0 0 0 0 1 1 1 11 0 0 0 0 1 0 0 0 0 0 0 1 12 0 0 0 0 0 1 0 0 0 0 0 1 20 0 0 0 0 0 0 1 1 1 1 1 1 21 0 0 0 0 0 0 0 1 1 0 0 1 22 0 0 0 0 0 0 0 0 1 0 0 1 30 0 0 0 0 0 0 0 0 0 1 1 1 31 0 0 0 0 0 0 0 0 0 0 1 1 32 0 0 0 0 0 0 0 0 0 0 0 1

Fig. 1 .

 1 Fig. 1. An nwa checking the Boolean XPath filter [//a[child::b]] by successful runs.

Fig. 3 .

 3 Fig. 3. Inference rules for the definition of acc A H sel

  with the Datalog program in Fig. 3. Proposition 4. The collection of values acc A H sel (p 1 , p 2 ) can be computed in time O(|Σ| • |A| 3 ) for every d nwa A.

Fig. 4 .

 4 Fig. 4. Generic eqa algorithm for a class E of query definitions.

Theorem 2 .

 2 For every d nwa A recognizing a canonical language over Σ × B n , and tree t ∈ T Σ , the time needed to process one event is in O((c+i)•|Σ|•|A| 2 ) and the space in O(c • d • |A|), where d = depth(t) is the depth of t, c = concur QA (t) and i = immediate QA (t).

Fig. 5 .

 5 Fig. 5. Semantics of XPath expressions.

Proposition 9 .

 9 The collection of values acc A HX (p 1 , p 2 ) with X ∈ {sel, rej} and p 1 , p 2 ∈ stat A can be computed in time O(|Σ| • |A| 3 ) for every d nwa A. Proof. The completion of the dnwa A is done in time O(|Σ| • |Γ A | • |stat A |). This bound is also a bound on the number of rules of A c , the completed automaton. The number of rules of the ground Datalog programs defining acc H sel and acc Hrej (see Fig. 3) are in O(|stat Ac | 3 + |rul Ac | • |stat Ac |). Then the saturation process of a ground Datalog program is in linear time.

Fig. 9 .

 9 Fig. 9. Algorithm computing univ X (a, γ, P )

Fig. 10 .

 10 Fig. 10. Construction of B sel from A and B

B

  sel is similar to a product automaton between A c and B c , the automata obtained after completion of A and B. Its number of rules and the time to compute it are both in O(|rul Ac | • |rul Bc |). The combination of Propositions 4 and 2 yields our main result:Theorem 5. Our eqa algorithm for answering queries Q (A,B) defined by a d nwas recognizing canonical language and schema of the query, applied to a tree t ∈ L(B) on the input stream, has the following costs:-precomputation in time O(|Σ| • |A| 3 • |B| 3 ) -time per step in O((c + i) • |Σ| • |A| 2 • |B| 2 ) where c = concur Q (A,B) (t) and i = immediate Q (A,B) (t) -space per step in O(c • d • |A| • |B|), where d = depth(t) is the depth of t

  (a), and B the nwa of Fig.11(b). We have Q 0 = Q A and S 0 = L(B).

  Fig. 11. Input nwas

Fig. 12 .

 12 Fig. 12. nwa B sel obtained from A and B (sink states are omitted)

Fig. 13 .

 13 Fig. 13. acc Hrej associated to Q 0 and S 0

Fig. 14 .

 14 Fig. 14. Run of the algorithm on a tree

  t ) % e ∈ E , t ∈ dom(Qe) l e t Q = Qe l e t c a n d i d a t e s = s e t . new ( ∅ )

	i n
	f o r η i n eve(t) i n s t r e a m i n g -o r d e r do
	c a n d i d a t e s . update ( η )
	f o r ν i n c a n d i d a t e s do
	i f ( ν , η ) ∈ s e l Q ( t )
	t h e n add-o u t p u t ( ν )
	c a n d i d a t e s . remove ( ν )
	e l s e i f ( ν , η ) ∈ r e j Q ( t )
	t h e n c a n d i d a t e s . remove ( ν )

)

  }| Proposition 2. For every d nwa A recognizing a canonical language over Σ × B n , and tree t ∈ T Σ , the time needed to process one event is in O((c+i)•|Σ|•|A| 2 ) and the space in O(c • d • |A|), where d = depth(t) , c = concur QA (t) and i = immediate QA (t).

Note that for sake of clarity, this construction does not hold for earliest selection of () at the start event, for Boolean queries. However, this case can be processed easily by considering every possible label of the root.

This is an overview without detection of rejection sufficiency. See Appendix D.

Acknowledgments. This work was partially supported by the Enumeration project ANR-07-blanc and the project CODEX of ANR-08-Defis.

Appendix B proves the hardness results for selection sufficiency. Appendix C proves the correctness of our sufficiency tests for dnwas, for both selection and rejection. Appendix D presents the details of our eqa algorithm for dnwas. Appendix E discusses the addition of schemas, also for the case of rejection. Finally, Appendix F presents a example run for our eqa algorithm.

Queries and Schemas in Unranked Trees

The set T Σ of unranked trees over a finite set Σ is the least set that contains all pairs a(t 1 , . . . , t m ) consisting of a letter a ∈ Σ and an hedge (t 1 , . . . , t m ) ∈ T m


Nicolas Petit
email: nicolas.petit@mines-paristech.fr

Control of a microfluidic separation process governed by the Zweifach-Fung effect

Keywords: Microfluidics, device integration technologies, process control applications, control of micro-and nano-systems, control of particulate processes, delay systems, non-smooth and discontinuous optimal control problems

This paper presents a microfluidic process of separation of a fluid containing particles. The control input is the ratio of flowrates in the two daughter channels of a bifurcation, which due to the Zweifach-Fung effect, has a direct but nonlinear effect on the particle volume fractions in the channels. The dead-volumes of the device and its capillary tubings cause an input-varying delay of hydraulic type. The paper presents several control problems of practical importance and formulates some concise problem statements for future research along with first simulation results.

INTRODUCTION

This article presents an example of a microfluidic system using the Zweifach-Fung effect to enrich or filter a fluid containing particles in suspension. The aim of the article is to present several control problems that are challenging and of practical interest.

Microfluidics is the science of manipulating and controlling fluids at Reynolds numbers under 1 in very small quantities (microliters to picoliters), in arrays of channels whose diameters are much smaller than 1 mm (from a few tens to a few hundreds of micrometers), see e.g. [START_REF] Tabeling | Introduction to microfluidics[END_REF]. Microfluidic systems are used in process engineering, chemistry and biotechnology among others. In these domains their ability to handle small volumes with high precision is an essential asset. Microfluidics is an enabling technology for many lab-on-a-chip applications, such as molecular analysis, chemical synthesis, biomanufacturing, drug screening, organ and tissue modeling, clinical diagnostic testing, virus detection and manipulation, etc. Microfluidic microsystems typically consist of complex arrays of channels, used to handle fluids in a way that allows them to interact, be mixed, measured, or encapsulated within each other, according to a desired process scheme. The network of channels consists of inlets, zigzag, cross, split, traps, pillars, among others typical architectures, see [START_REF] Paratore | Reconfigurable microfluidics[END_REF] for a state-of-the-art overview. The fluid mechanics at stake in microfluidic systems is highly dependent on the complex geometry of the network. A phenomenon that has received particular attention in this field is the Zweifach-Fung effect (see [START_REF] Fung | Microcirculation: mechanics of blood flow in capillaries[END_REF]), a.k.a. bifurcation law. It can be described as follows (see [START_REF] Doyeux | Behavior of flowing bodies near a bifurcation: Elucidating the Zweifach-Fung effect[END_REF][START_REF] Doyeux | Spheres in the vicinity of a bifurca-tion: elucidating the Zweifach-Fung effect[END_REF]): when a suspension of particles reaches an asymmetric bifurcation, the particles volume fractions in the two daughter branches are not equal. In details, for branches of comparable geometrical characteristics, but receiving different flowrates, the volume fraction in particles increases in the high flowrate branch.

Interestingly, this effect can serve to engineer sorting or purification devices, see e.g. [START_REF] Yang | A microfluidic device for continuous, real time blood plasma separation[END_REF]. In such systems, channels have square section of 40 µm, lengths of 20 mm. Volumes to be treated are 30 µL over 30 min and the purification requirements are s.t. concentration must be handled with an accuracy of 1 %. Many studies have concentrated on establishing empirical and theoretical laws describing the separation of particles in the two daughter branches of the main channel. Depending on various parameters such as widths, angles of the branches and size of particles, several semi-analytical laws have been proposed to describe the particle volume fraction in the two branches as a function of the flowrate ratios between them, see e.g. [START_REF] Dellimore | Ratio of cells and plasma in blood flowing past branches in small plastic channels[END_REF]; [START_REF] Guibert | A new approach to model confined suspensions flows in complex networks: application to blood flow[END_REF]. One can refer to [START_REF] Doyeux | Behavior of flowing bodies near a bifurcation: Elucidating the Zweifach-Fung effect[END_REF] for a comprehensive analysis of these laws. This paper exposes some control challenges worth investigating for controlling such a process governed by the Zweifach-Fung effect. The simplest microfluidic set-up one can consider is pictured in Fig. 1. A main channel is used to transport a suspension contained in a (inlet) reservoir. Then, it reaches a bifurcation consisting of two equal dimension daughter branches. The bifurcation at stake is a T-shaped bifurcation (alternatively a Y-shape could be considered without loss of generality, see again [START_REF] Doyeux | Behavior of flowing bodies near a bifurcation: Elucidating the Zweifach-Fung effect[END_REF]). The main channel and its daughter branches are contained in a single microfluidic chip . The inlet of the main channel and the outlets of the branches are connected through capillary tubings to three reservoirs. The pressures at the three ports of the microfluidic chip are controlled (because the reservoirs are pressurized with a high level of accuracy, and the fluid is incompressible) so that the flowrates can be chosen. In the control problems under consideration in this article, the output of interest is the volume fraction in one of the output reservoirs, which can be controlled by changing the ratio between the flowrates of the daughter branches.

The paper is organized as follows. In Section 2, we briefly detail the model, and present a concise set of equations governing the system. The key properties of the dynamics is that it is nonlinear, mostly due to the Zweifach-Fung effect, and are subjected to an input-varying delay of hydraulic type. In Section 3, we illustrate some of its surprisingly complex behavior, in open loop. In Section 4 we expose the main challenges for application of optimization based techniques such as Model Predictive Control.

P 0 Q 1 (< Q 2 ) Q 2 P 1 P 2 Q 0 Fig. 1.
Separation process using the Zweifach-Fung effect. A fluid containing particles flows from the inlet reservoir through a microfluidic device within which it reaches a bifurcation and finally flows to the outlet reservoirs. The flowrates Q 0 , Q 1 , Q 2 are controlled by the pressures P 0 , P 1 , P 2 in the reservoirs. In Section 5, we discuss closed-loop stabilization. Some conclusions and perspectives are given in Section 6.

MODEL OF THE DYNAMICS

Consider the system pictured in Fig. 1. Note Q 0 , Q 1 , Q 2 the (volume) flowrates in the input, and two daughter (output) channels (1 and 2). The fluid (suspension) contained in the reservoir consists of a solvent and particles. Using pressure controllers, it can be considered that the ratio

u = Q 1 Q 0 ∈ [0, 1] is a control variable while Q 0 is kept constant. Conser- vation of volume implies that Q 2 = Q 0 -Q 1 .
When u is changed, then the volume fraction after the bifurcation point is altered. Define f (u) the volume fraction in channel 1 (right after the bifurcation). Its graph is of the form presented in Fig. 2 (adapted from [START_REF] Doyeux | Spheres in the vicinity of a bifurca-tion: elucidating the Zweifach-Fung effect[END_REF]).

Because the daughter channels have similar geometries, the function f is symmetric.

The outlet of channel 1 flows in an incompressible manner, with no back mixing, into a reservoir. The reservoir contains a volume v of particles which dynamics is

v = f (u(t -D(t))) Q 0 u (1)
where D is a hydraulic delay corresponding to the volume V 0 of channel 1 (from the bifurcation to the reservoir, thought the capillary tubing). As for many systems involving transportation of material, see e.g. Bresch-Pietri and Petit (2016); [START_REF] Chèbre | Feedback control and optimization for the production of commercial fuels by blending[END_REF], a delay appears in the dynamics which is defined through an implicit integral equation1 . Such delays are referred to as hydraulic delays. In Eq. ( 1), this delay is visible on the volume fraction as it propagates without being altered in the channel (there is no back mixing), but not to the flowrate which is uniform in the channel due to incompressibility. The implicit equation is

t t-D(t) u(τ )dτ = Γ V 0 Q 0 > 0 (2)
The output of interest is the volume fraction in the reservoir. Assuming it is empty at t = 0, one has

y(t) = 1 Q 0 v t 0 u(τ )dτ = t 0 f (u(τ -D(τ ))u(τ )dτ t 0 u(τ )dτ
In practice, y can be measured. A cytometer is located at the outlet of channel 1, after the hydraulic delay. These notations allow us to formulate a first problem of practical interest for this microfluidic separation system. Problem 1. Consider the two states systems ẋ1

(t) = f (u(t -D(t))u(t), ẋ2 (t) = u(t), with single output y(t) = x 1 (t)/x 2 (t) and single input u(t) ∈ [0, 1]
, find a closed loop controller able to asymptotically stabilize any feasible setpoint.

OPEN LOOP BEHAVIOR

The system described in Problem 1 has a surprisingly complex behavior. For example, its transient responses to a positive step and to a negative step vastly differ (parameter Γ was set to 1). These differences are illustrated in are below the typical settling time of 5 s for this system setup. The figures report the right-hand sides of the first state differential equation in response to various square signals. The two culprits of the observed dissimilarities are the nonlinearity f (generating an expected nonlinear asymptotic gain, visible in Fig. 4) and the time-varying delay depending on the input whose effects include the possible appearance of a strong peak when the delay is reduced (see Fig. 3). These simulation results are obtained using a method discussed below.

Numerical simulation of the dynamics

To obtain reliable simulation results of the input-dependent varying delay dynamics, special care is required on the numerical side. As noted in [START_REF] Clerget | Contributions to the control and dynamic optimization of processes with varying delays[END_REF], delays require specific tools in their numerical simulation. A rich body of literature has long studied the numerical simulation of delay-differential algebraic equations (DDAE). Useful references can be found in [START_REF] Banks | Spline approximations for functional differential equations[END_REF], [START_REF] Karoui | Computer solutions of state-dependent delay differential equations[END_REF] or [START_REF] Ascher | The numerical solution of delay-differential-algebraic equations of retarded and neutral type[END_REF].

A classic idea is to replace it with the underlying transport equation governing the system (e.g. [START_REF] Shi | Optimization of grade transitions in polyethylene solution polymerization processes[END_REF]).

Formally, this change of representation does not generate any approximation (equation ( 2) is the exact solution of the PDE, see Bresch-Pietri ( 2012)).

In turn this requires the discretization of the transport PDE. It is well-known that good numerical schemes can be obtained for transport phenomena using finite volumes methods (see [START_REF] Leveque | Finite Volumes Methods for Hyperbolic Problems[END_REF]). Classically, space is divided into a set of cells over which averaged properties are defined.

The approach described in [START_REF] Agarwal | Advanced Strategies for Optimal Design and Operation of Pressure Swing Adsorption Processes[END_REF] based on the use of the Method of Lines (MOL) by discretizing the PDE only with respect to space into a set of ordinary differential equations can be used. It is a second-order accurate scheme defined over a regular mesh.

Comparable results can be obtained using a full discretization approach (both w.r.t. time and space) using the following a second order accurate scheme. To obtain reliable results, it should be remembered that this type of finite volumes numerical schemes is stable only if the Courant-Friedrichs-Lewy (see e.g. [START_REF] Allaire | Numerical analysis and optimization: an introduction to mathematical modelling and numerical simulation[END_REF]) condition is verified (bearing on ∆t the step size and ∆x the spatial resolution). This condition is instrumental in setting up the numerical scheme.

OPTIMIZATION BASED-CONTROL

Considering the relative simplicity (more precisely the conciseness) of the formulation of Problem 1, it is tempting to try to solve it with a classic Model Predictive Control methodology, see for example [START_REF] Sbarciog | Nonlinear predictive control of processes with variable time delay. a temperature control case study[END_REF] for a typical application to a related problem. Even if the discussion about the non symmetric nature of the system behavior near equilibrium presented in Section 3 might stress some possible difficulty, a main obstruction has not been discussed yet.

The system controllability remains to be established although the first part of the dynamics has already been studied and be shown to be controllable in a very general sense. This point is discussed below in Section 4.1. However, a more hidden pitfall is that any general optimal control problem formulated for the dynamics of problem 1 is (most likely) non smooth and will therefore reveal particularly troublesome for numerical solvers in its present form. This point is covered in Section 4.3.

Motion planning

The dynamics under consideration is actually close to the dynamics of blending (or dilution dynamics) studied in other contexts. Adding functions composition and inversion to the usual algebraic computation rules, it was shown in [START_REF] Petit | Motion planning for two classes of nonlinear systems with delays depending on the control[END_REF] that such systems are controllable in the sense of [START_REF] Willems | Paradigms and puzzles in the theory of dynamical systems[END_REF], i.e. that their trajectories could be explicitly parameterized in the sense of flat systems (see [START_REF] Fliess | A Lie-Bäcklund approach to equivalence and flatness of nonlinear systems[END_REF]) so that from a prescribed past trajectory on ] -∞, 0] a trajectory could be constructed on [0, T ] for some T > 0 connecting to a future trajectory over [T, +∞[. In these systems, the flat output under consideration is

Y (t) = t 0 u( )d
This variable serves to parameterize several of the variables at stake here. Indeed

Y (t) -Y (t -D(t)) = Γ which gives D(t) = t -Y (-1) (Y (t) -Γ)
which is legit as Y can be assumed strictly monotonic when u > 0, and thus is invertible. Here, the two additional states x 1 and x 2 can be defined by integration (up to some initial condition) of right-hand sides solely defined by Y past values.

ẋ1 = f ( Ẏ (Y (-1) (Y (t) -Γ)) Ẏ (t), ẋ2 = Ẏ (t)
to account for the initial conditions in the reservoir. Motion planning can be readily addressed by means of scheduling a smooth and monotonic trajectory for Y , the end points and the transient of which being determined according to the desired target in the reservoir.

The relation above also shows that the delay can be easily bounded by assumptions on Y and its inverse. It gives, under some appropriate assumptions, see again [START_REF] Petit | Motion planning for two classes of nonlinear systems with delays depending on the control[END_REF], that the transient is achieved in finite time. In practice this controllability result is only a first step, and optimal transients are desired. This is discussed next.

Two optimal control problems of practical interest

A first problem of practical interest is to reach a desired concentration in the reservoir in minimum time. The solution might not be a simple as one can anticipate it due to the properties of the function f governing the separation at the bifurcation point. Problem 2. Consider the input-output description of Problem 1 and some initial conditions for x 1 , x 2 , and some past values for u. Let y sp ∈ (0, 1), solve min T , where T is s.t. y(T ) = y sp .

A second problem of interest expresses an optimal output tracking problem while limiting the variations of the control. To formulate this, a state extension is considered. Problem 3. Consider the input-output description of Problem 1 and some initial conditions for x 1 , x 2 , and some past values for u. Further consider the extra dynamic u = v. Let y sp ∈ (0, 1), solve min T 0 ||y(t) -y sp || 2 + w||v(t)|| 2 dt for some fixed parameters w > 0 and T > 0.

Non smoothness related to hydraulic delays

Strictly speaking, the study of the calculus of variations for optimal control problems subject to time-varying delays in the dynamics is not a new subject. At first, it seems that the historical results of [START_REF] Banks | Necessary conditions for control problems with variable time lags[END_REF]; [START_REF] Asher | Optimal control of systems with state-dependent time delay[END_REF], which can be seen as an extension to [START_REF] Hughes | Variational and optimal control problems with delayed argument[END_REF] given for fixed delays, could be applied to solve Problem 2 and Problem 3. Indeed in this seminal work, necessary stationarity conditions were derived for a system subject to multiple fixed time-varying delays (i.e. depending once for all on t only and not on the state nor the control).

However, the dependency of the delay on the input make these results incomplete and some extra terms, possibly non-smooth appear. By expressing all the mutual interactions between the variables, it was shown in [START_REF] Clerget | Optimal control of systems subject to input-dependent hydraulic delays[END_REF] under which condition such an optimal control problem for a system subjected to a hydraulic delay is Gâteaux differentiable. It was also shown that this input dependency of the delay generally make the system violate these conditions.

To treat such optimal control problems, it was suggested to introduce a (smooth) regularized version of the problem and derive its stationarity conditions. The regularization can be shown to converge, i.e. it produces a sequence of solutions converging in a functional sense to the actual non-smooth solution when the regularization parameter is gradually reduced. Interestingly, this latter result can be seen as a refinement of the results of the pioneer work of [START_REF] Asher | Optimal control of systems with state-dependent time delay[END_REF] to the case of an hydraulic delay, under regularization. The sequence consists of fixed timevarying delayed optimal control problems. Each of these problems is defined using a sensitivity analysis stemming from the adjoint equations defined by the calculus of variations. A penalty term prevents the control from deviating too much between the two consecutive problems in the sequence, and a strong convexity results guarantees convergence.

The general optimal control problem covered by the previously described study is as follows. We recall it to highlight the role of the delay dependency.

Let φ : R p → R * + be a smooth function. Take some initial conditions (over a finite past

) (u 0 , x 0 ) ∈ C 1 pw ([r 0 ; 0], R p ) × D 1 ([r 0 ; 0], R p ), r 0 < 0 with 0 r0 φ (u 0 (τ )) dτ = 1. Consider the optimal control problem with input-dependent delays min u T 0 L(t, x(t), u(t)) dt + ψ(x(T )) J 0 (u) s.t. ∀t ∈ [0; T ], ẋ(t) = f (t, x(t), x(r u (t)), u(t), u(r u (t))) x [r0;0] = x 0 , u [r0;0] = u 0
where r u is defined by the relation t ru(t) φ(u(τ )) dτ = 1. The following useful preliminary result stresses the main issue of general non-differentiability Proposition 1. Sensitivity of hydraulic delay w.r.t. input variations [START_REF] Clerget | Dynamic optimization of processes with time varying hydraulic delays[END_REF] Similarly, for any t ∈ [0; r u (T )[

lim δ→ s 0 r -1 u+δh (t) -r -1 u (t) δ = - 1 lim τ → s r -1 u (t) φ(u(τ )) r -1 u (t) t ∂φ ∂u (u(τ ))h(τ ) dτ
where

s = sign -s • r -1 u (t) t ∂φ ∂u (u(τ ))h(τ ) dτ
and if u is continuous at r -1 u (t) (which is not need), the Gâteaux derivative is given by

D h r -1 u (t) = - 1 φ(u(r -1 u (t))) r -1 u (t) t ∂φ ∂u (u(τ ))h(τ ) dτ
This last expression can be checked to see the jumps.

On the algorithm side, the resolution of the successive problems can be performed using a direct collocation transcription method (see e.g. [START_REF] Biegler | Solution of dynamic optimization problems by successive quadratic programming and orthogonal collocation[END_REF]), with AMPL as algebraic modeling language and IPOPT as NLP solver (see details in [START_REF] Clerget | Contributions to the control and dynamic optimization of processes with varying delays[END_REF]). Adjoint equations are resolved through a discretization scheme and used to formulate the next problem in the sequence.

CLOSED-LOOP CONTROL

This last section finishes the panorama of basic questions of control interest for the separation process under consideration.

Stabilisation by means of small gains

To a desired reference for the output, there corresponds a constant value for ẋ1 and one (possibly several depending on the function f ) setpoint for u. Problem 1 can be treated, using a small gain controller, in a vicinity of the initial conditions. Indeed, assuming that the initial conditions correspond to a non zero value of the derivative of f , then the dynamics of x 1 can be approximated, for some α > 0, = 0

ẋ1 = (α + u(t -D(t))u(t), ẋ2 = u(t) (3) y(t) = x 1 (t)/x 2 (t) (4)
A linearizing feedback can be easily derived so that x 1 tracks any given feasible and constant reference. Because this reference is not varying, then it can be shown that the linearizing feedback strategy is always feasible. A sequence of cascaded inequalities could be established, as in [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay with jumps[END_REF], to prove that, in turn, the delay remains within some specified bounds. These bounds can serve to define a sequence of time intervals over which uniform w.r.t. time bounds can be established.

A conservative bound on the initial condition is usually sufficient to grant asymptotic convergence, by breaking the inter-dependency of the cascade of inequalities. It serves to bound the value of and to use this bound in the definition of the initial condition on the states x 1 . However, to account for the second state x 2 in the definition of y it is necessary to bias the reference signal of x 1 or to increase the gain over time. This causes more advanced difficulties.

An example of performance obtained with a linear saturated controller is pictured in Fig. 5 for a step change of the output setpoint to y sp = 0.6.

Sampled measurement feedback

Measurement of the concentration y is usually performed using one of the current cytometry technique, among which are image cytometers, flow cytometers and timelapse cytometers, see e.g. [START_REF] Mckinnon | Flow cytometry: an overview[END_REF]; [START_REF] Han | Imaging technologies for flow cytometry[END_REF]. These techniques all have relatively long processing times, and can only treat fluid samples outside of the reservoir, causing an additional lag. Therefore, a formula representing these specifities and limitation is to model the measurement of y as follows y meas (t i ) = y(t i -D m (t i )) + ε i where information is only available at instants t i (forming an increasing sequence going to ∞, almost ideally spaced over a regular time grid) and D m (t i ) is a measurement delay, which can be considered as randomly distributed as in [START_REF] Kong | Constant time horizon prediction-based control for linear systems with time-varying input delay[END_REF] or depending on the value of y itself as in Bekiaris-Liberis and Krstic (2013b,a). A stochastic framework to model the noise ε i is required, see e.g. [START_REF] Min | Outputfeedback control for stochastic nonlinear systems subject to input saturation and time-varying delay[END_REF]. The fact that the delay in the dynamics changes when the control changes complexifies significantly the analysis beyond what is usually considered, see e.g. [START_REF] Choi | Output feedback regulation of a chain of integrators with an unknown timevarying delay in the input[END_REF].

CONCLUSION AND PERSPECTIVES

The purpose of this paper is to highlight a simple yet surprisingly rich and difficult to control nonlinear dynamics under input varying delay of hydraulic type. This microfluidic system has some great interest in the community of lab-on-chips and there is little doubt that controlling it with a high level of performance, fast transients and strong disturbance rejection capabilities could be very beneficial in many situations where the handled fluids have very high costs, such as stem cells for example as is done in many biological applications Zhang et al. (2012); [START_REF] Zhang | Applications of microfluidics in stem cell biology[END_REF]. It is believed that a sophisticated predictorbased controller could solve Problem 1. On the other hand Problem 2 and Problem 3 could be directly addressed by the recent results on optimal control of such systems. Microfluidics devices handle very tiny volumes but their time constants are macroscopic (of the order of 1 or 2 sec), so it is not unlikely that online optimization should be possible. Finally, the sampling issue discussed in Section 5.2 remains vastly opened but of critical importance at the light of current measurement systems noises.

  in 13th IFAC Symposium on Dynamics and Control of Process Systems, including Biosystems 2022

Fig. 2 .

 2 Fig. 2. Two examples of possible functions bifurcation lawsf . Blue: (adapted from[START_REF] Doyeux | Spheres in the vicinity of a bifurca-tion: elucidating the Zweifach-Fung effect[END_REF]. Red: (sinusoidal) simplified version.

Fig. 4 .Fig. 3 .

 43 Fig. 4. Long-duration square signals showing a non symmetric responses to step signals (top: input signals, bottom: right-hand sides of the first state differential equation).

Fig. 5 .

 5 Fig. 5. Closed-loop performance on Problem 1.

This equation stems from an exact resolution of the transport partial differential equation with variable velocity, (Bresch-Pietri and Petit,

2016, Lemma 1.1).