Olivier Gauwin

Joachim Niehren

Sophie Tison

Queries on Xml Streams with Bounded Delay and Concurrency

Keywords: streaming, tree automata, Xml, databases, XPath

Query answering algorithms on

Xml streams check answer candidates on the fly in order to avoid the unnecessary buffering whenever possible. The delay and concurrency of a query are two measures for the degree of their streamability. They count the maximal number of stream elements during the life time for some query answer, and respectively, the maximal number of simultaneously alive answer candidates of a query. We study queries defined by deterministic nested word automata, which subsume large streamable fragments of XPath subject to schema restrictions by DTDs modulo P-time translations. We show that bounded and k-bounded delay and concurrency of such automata-defined queries are all decidable in polynomial time in the size of the automaton. Our results are obtained by P-time reduction to the bounded valuedness problem for recognizable relations between unranked trees, a problem that we show to be decidable in P-time.

Introduction

Streaming algorithms are relevant for Xml databases and data exchange, whenever large data collections that cannot be stored in main memory are to be processed. Instead data is communicated over streams and processed on the fly. Recently, Xml streaming algorithms were proposed for schema validation [START_REF] Segoufin | Validating streaming XML documents[END_REF] (membership in tree languages), one-pass typing [START_REF] Martens | Expressiveness and complexity of XML schema[END_REF] (annotating nodes of trees by types), and query answering [START_REF] Kumar | Stream processing of XPath queries with predicates[END_REF][START_REF] Fernandez | XQuery streaming à la carte[END_REF][START_REF] Benedikt | Efficient and expressive tree filters[END_REF][START_REF] Benedikt | Stream Firewalling of XML Constraints[END_REF][START_REF] Gauwin | Streaming Tree Automata and XPath[END_REF].

An Xml streaming algorithm inputs a linearization of an Xml document (as a series of events) on an external stream, computes its output incrementally, and writes it to an external output device. The document on the stream is processed in a single reading pass. A central quality criterion of streaming algorithms is memory efficiency. In the best case, the required space should be independent of the size of the input document. Furthermore, the time complexity should be polynomial in the size of the query, in the space that is required, and in the size of the output that is produced. We refer to [START_REF] Gauwin | Streamable fragments of Forward XPath[END_REF] for a discussion of streamability notions for query languages that capture all these aspects.

Streaming algorithms for a given Xml query compute the answer set of the query on the fly. They can be understood as some kind of pushdown transducers that operate on linearizations of Xml documents. Their space complexity depends on the number of states, the size of the pushdown which of is often bounded by the depth of the tree, and the maximal number of answer candidates stored in main memory simultaneously.

Bounded Concurrency and Delay

The concurrency of an n-ary node-selection query is the maximal number of simultaneously alive answer candidates while processing the stream [START_REF] Bar-Yossef | Buffering in query evaluation over XML streams[END_REF]. An answer candidate is alive at an event of the input stream, if it can still be selected in some continuation of the stream and rejected in some other. Hence the selection and rejection of this candidate cannot be decided at this event. Note that the notions of aliveness and concurrency do only depend on the query and not on the particular query answering algorithm. The concurrency of a monadic query is a lower bound for the space requirement of any streaming algorithm that answers the query on realistic machine [START_REF] Gauwin | Streaming Tree Automata and XPath[END_REF][START_REF] Gauwin | Streamable fragments of Forward XPath[END_REF], or on unrestricted machine models for restricted query languages [START_REF] Bar-Yossef | Buffering in query evaluation over XML streams[END_REF].

The delay of a query is a lower bound for waiting times on query answers, i.e., the maximal number of events between visiting and selecting an answer element on the stream. Queries with bounded delay permit high quality query answering algorithms, where the waiting time for query answers is bounded. We will see that bounded delay implies bounded concurrency for monadic node selection queries (but not for binary queries).

Relevance for XPath Queries.

We illustrate the relevance of bounded and k-bounded delay and concurrency in practice at a sample of XPath queries on Xml documents. These documents represent bibliographies satisfying the following Dtd:

B -> P* P -> T A* T -> #PCDATA A -> #PCDATA

This schema definition states that a bibliography (B) is a list of publications (P), that a publication is a pair of a title (T) and a list of authors (A), and that titles and authors are data values. Publications can thus be abstracted into flat unranked trees such as for instance:

P(T('found. of databases'),A('abiteboul'),A('hull'),A('vianu'))

The corresponding Xml stream is a list of opening tags, closing tags, and data values, i.e. the following word:

A streaming algorithm for Q1 can select all T-nodes of bibliographies t immediately at opening time (i.e. when reading the opening tag <T>), so with delay 0. All other nodes can be immediately rejected at opening time, so the concurrency is 0 too. The next query Q2 selects all publications whose title contains the substring 'XML'. Q2 satisfies delay(t) ≤ 2 and concur (t) ≤ 1 for all bibliographies t: Q2: //P[T[contains(.,'XML')]]

In order to decide the selection of a P-node of a bibliography t, the subsequent T-node must be opened, and then the subsequent data value must be read. The delay of t is thus bounded by 2. At any time point at most one title node must be stored so the concurrency is at most 1.

Next, we consider the query Q3 that selects all co-authors of 'abiteboul' in some publication with at most 10 authors. It satisfies for all bibliographies t that delay(t) ≤ 28 and concur (t) ≤ 9:

Q3: //P[count(A)<=10 and A[text()='abiteboul']]/ A[not(text()='abiteboul')]

In order to decide the selection of an A-node in a bibliography t, in the worst case one might have to inspect the data values of 9 follow-up A-nodes. The delay thus contains at most 9 opening A-nodes, 9 closing A-nodes, and 10 data value nodes, and it thus bounded by 28. The number of candidates that are to be stored at the same time point may be at most 9 since at most 9 A-nodes may be undecided simultaneously, so the concurrency is bounded by 9.

We now consider the query Q4 that selects all co-authors of 'abiteboul' in some publication. Here both the delay and concurrency are unbounded for varying bibliographies, i.e., sup t delay(t) = sup t concur (t) = ∞:

Q4: //P[A[text()='abiteboul']]/A[not(text()='abiteboul')]

Since the number of authors of a publication may be unbounded a priori, the delay of selection may be unbounded and also the concurrency. This illustrates that many practically streamable queries do not have bounded concurrency. In this case however, it is often possible to rewrite the query as done for Q4 in Q3 or else the schema in order to restrict node selection to documents admissible in practice.

Query Q5 selects all publications whose last author is 'abiteboul'. It satisfies sup t delay(t) = ∞, even though concur (t) ≤ 1 for all bibliographies t.

Q5: //P[A[text()='abiteboul' and not(following-sibling::A)]]

This is an example of a query with a unbounded delay but small concurrency. The converse is false for monadic queries, where bounded delay always implies bounded concurrency. This fact may be relevant in cases where deciding bounded delay is more costly than deciding bounded concurrency.

All queries above except for Q3 and Q5 belong to the finitely streamable fragment of Forward XPath distinguished in [START_REF] Gauwin | Streaming Tree Automata and XPath[END_REF][START_REF] Gauwin | Streamable fragments of Forward XPath[END_REF] where the branching width of the path expression is bounded by 3 (modulo considering data values as tags) and can thus be compiled in polynomial time to deterministic nested word automata (dnwas) [START_REF] Alur | Adding nesting structure to words[END_REF]. What is needed to capture Q3 and Q5 in addition is a streamable extension of these fragments of XPath with next-sibling axis.

It should also be noticed that flat unranked trees are essentially words since they contain no relevant nesting structure so that one can remove all closing tags. Therefore it is natural to start our study of streaming algorithms for queries defined by deterministic finite automata (dfas) on words, and only to move to queries on nested words (trees) defined by dnwas in a second step.

Contributions.

In this paper, we show that bounded delay and bounded concurrency are both decidable in P-time for n-ary queries and schemas defined by dnwas [START_REF] Alur | Adding nesting structure to words[END_REF][START_REF] Alur | Marrying words and trees[END_REF][START_REF] Alur | Visibly pushdown languages[END_REF]. Queries by dnwas subsume large streamable fragments of XPath [START_REF] Gauwin | Streaming Tree Automata and XPath[END_REF][START_REF] Gauwin | Streamable fragments of Forward XPath[END_REF] with schema restrictions defined by dnwas, and thus with extended Dtds with restrained competition [START_REF] Murata | Taxonomy of XML schema languages using formal language theory[END_REF][START_REF] Martens | Expressiveness and complexity of XML schema[END_REF].

It should also be noticed that schema restrictions may be essential to reduce delay and concurrency, as they permit to restrict the set of possible continuations of Xml streams. The choice of dnwas as automata notion for unranked trees is equally justified by their generality: dnwas subsume bottom-up deterministic tree automata that operate on bottom-up binary encodings of unranked trees (currying) and on top-down deterministic tree automata operating on topdown encodings of unranked trees (first-child next-sibling encoding). These relationships are worked out in the appendix in more details.

In the subcase of dfa queries on words (or flat unranked trees), we can reduce bounded delay and concurrency of dfa-queries on words in P-time to bounded ambiguity of finite automata, which can be decided in cubic time [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF][START_REF] Allauzen | General algorithms for testing the ambiguity of finite automata[END_REF]. The algorithm for dfa queries on words, however, cannot be lifted to dnwa queries on trees in any straightforward manner, mainly since dnwas have stacks in contrast to dfas. In particular, it seems not sufficient to replace bounded ambiguity of nfas by bounded ambiguity of nwas or of tree automata on ranked trees. Instead, we propose another solution by reduction to bounded valuedness of bottom-up tree transducers for ranked trees.

A central idea of our reduction is to define aliveness of automata queries on unranked trees by recognizable relations between unranked trees [START_REF] Benedikt | Logical definability and query languages over ranked and unranked trees[END_REF]. More precisely, we define the aliveness for a dnwa query A by a possibly non-deterministic nwa B of size polynomial in the size of A. The most surprising point here is polynomiality, in particular since the direct construction of a dnwa for aliveness from [START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF] produced dnwas of exponential size. Instead, we propose to construct a non-deterministic nwa B by an existential fo-logic formula over basic recognizable relations depending on A. The restriction to existential fo-formula is crucial to obtain a definition in P-time. Indeed, we conjecture that B cannot always be constructed deterministically from A without growing exponentially.

As an intermediate result of its own interest, we show that bounded valuedness of recognizable relations between unranked trees is decidable in P-time. This result can be reduced in P-time to the analogous result for recognizable relations between ranked trees [START_REF] Tison | Automates Comme Outils de Décision dans les Arbres[END_REF] via binary encoding of unranked trees. We then present a further P-time reduction to bounded valuedness of bottom-up tree transducers for ranked trees, which can be decided in P-time [START_REF] Seidl | Single-valuedness of tree transducers is decidable in polynomial time[END_REF].

We also show for fixed k that k-boundedness of nwa-recognizable relations can be decided in P-time. Our decision procedure relies on direct automata construction. Note that it is open whether the more general problem of kbounded valuedness of bottom-up tree transducers is decidable in P-time. The best algorithm so far is in coNP-time [START_REF] Seidl | Equivalence of finite-valued tree transducers is decidable[END_REF].

We added some new results to the Lata conference version [START_REF] Gauwin | Bounded delay and concurrency for earliest query answering[END_REF] of the present article. First, we showed that k-bounded delay and concurrency for fixed k can be decided in P-time (Theorem 6), by proving that k-bounded valuedness of binary recognizable relations is decidable in P-time (Theorem 7). Second, we proved the exptime-hardness of deciding whether a binary recognizable relation has k-bounded valuedness, when k is variable (Theorem 9). Third, we added the result that bounded delay implies bounded concurrency for monadic queries (Proposition 6). Fourth, we now show in the case of words, how to compute the delay efficiently, and thus how to decide k-bounded delay efficiently (Theorem 4). Examples and complete proofs were added.

Related Work

While usual evaluation algorithms store the whole Xml document in main memory [START_REF] Gottlob | Efficient algorithms for processing XPath queries[END_REF][START_REF] Parys | XPath evaluation in linear time with polynomial combined complexity[END_REF], on-the-fly evaluation algorithms on Xml streams start processing input data before it is completely received [START_REF] Segoufin | Validating streaming XML documents[END_REF][START_REF] Barton | Streaming XPath Processing with Forward and Backward Axes[END_REF][START_REF] Chen | An Efficient XPath Query Processor for XML Streams[END_REF][START_REF] Peng | XSQ: A streaming XPath engine[END_REF][START_REF] Josifovski | Querying XML streams[END_REF][START_REF] Wu | Evaluating Partial Tree-Pattern Queries on XML Streams[END_REF]. The ideal of on-the-fly algorithms with optimal memory management [START_REF] Bar-Yossef | On the memory requirements of XPath evaluation over XML streams[END_REF] lead to the idea of earliest query answering (Eqa), whose objective is to keep only alive answer candidates in main memory [START_REF] Berlea | Online evaluation of regular tree queries[END_REF][START_REF] Bar-Yossef | Buffering in query evaluation over XML streams[END_REF][START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF]. The memory consumption of Eqa algorithms thus directly depends on the concurrency of the query.

Many evaluation algorithms for XPath fragments on Xml streams subscribe to the idea of Eqa [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] Gou | Efficient algorithms for evaluating XPath over streams[END_REF][START_REF] Nizar | Efficient Evaluation of Forward XPath Axes over XML Streams[END_REF][START_REF] Prakash Ramanan | Worst-case optimal algorithm for XPath evaluation over XML streams[END_REF]. However, it turned out recently [START_REF] Benedikt | Stream Firewalling of XML Constraints[END_REF][START_REF] Gauwin | Streaming Tree Automata and XPath[END_REF], that Eqa is infeasible, even for small fragments of XPath, for which satisfiability or universality cannot be decided in P-time. As a consequence, Benedikt et al. [START_REF] Benedikt | Stream Firewalling of XML Constraints[END_REF] propose streaming algorithms for a restricted fragment of XPath, where queries can never look forward, so that node selection can always be decided immediately (i.e., the delay is zero).

Gauwin et al. [START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF] present an Eqa algorithm for queries defined by dnwas or equivalently, by deterministic visibly pushdown automata [START_REF] Alur | Visibly pushdown languages[END_REF], streaming tree automata [START_REF] Gauwin | Streaming tree automata[END_REF], or pushdown forest automata [START_REF] Neumann | Locating matches of tree patterns in forests[END_REF]. Berlea's Eqa algorithm for queries defined by pushdown forest automata [START_REF] Berlea | Online evaluation of regular tree queries[END_REF] assumes infinite alphabets, which removes the algorithmic hardness of Eqa for non-deterministic automata, but limits its relevance at the same time.

Recognizable relations for ranked trees [START_REF] Tison | Automates Comme Outils de Décision dans les Arbres[END_REF][START_REF] Hubert Comon | Tree automata techniques and applications[END_REF] were applied for instance, in order to decide the first-order theory of ground tree transducers [START_REF] Dauchet | The theory of ground rewrite systems is decidable[END_REF]. The closure operations of tree automata correspond to the first-order closure properties of recognizable relations. Recognizable relations for unranked trees were introduced in [START_REF] Benedikt | Tree extension algebras: Logics, automata, and query languages[END_REF][START_REF] Benedikt | Logical definability and query languages over ranked and unranked trees[END_REF]. They showed that all recognizable relations between unranked trees can be defined in the first-order logic of unranked trees with two extension operators, downwards and to the right. Note however, that their results are restricted to recognizable relations between trees over the same signature, while we need different signatures in the current article. Furthermore, the problem of bounded valuedness of recognizable relations is not studied there.

Outline.

We recall needed known boundedness results for word or tree automata and transducers in Section 2. In Section 3, we recall how to map queries on relational structures to canonical languages of annotated elements of the domain of the structure. This mapping is well-known from the relationship between logic and automata for words or trees. In Section 4, we discuss streaming algorithms for query answering and recall the notions of concurrency and delay. In Section 5, we show how to decide bounded delay and concurrency for dfaqueries in words (aka flat unranked trees) by reduction to bounded ambiguity of nfas. This section is not essential for our main results on more general dnwa queries on unranked trees, but illustrates the nature of the problems and provides some stronger results for this special case. In Section 6, we formulate our main results for dnwa-defined queries (Theorem 6). In Section 7, we discuss bounded valuedness problems for recognizable relations between unranked trees. In Section 8, we show how to define delay and concurrency as recognizable relations in P-time.

Bounded Ambiguity and Valuedness

We recall some results from the literature that we will make use of later on. They concern the bounded ambiguity for automata on words and trees and the bounded valuedness of tree transducers. The classes of trees considered there are all ranked, but these results will be used to prove properties of relations over unranked trees.

Bounded Ambiguity of Finite Automata

A finite automaton (nfa) over Σ is a tuple A = (stat, init, rul , fin) where init, fin and stat are finite sets with init, fin ⊆ stat, and rul ⊆ stat 2 × (Σ ∪ {ǫ}) contains rules that we write as q a → q ′ or q ǫ → q ′ where q, q ′ ∈ stat and a ∈ Σ. Whenever necessary, we will index the components of A by A. Let the size of A count all states and rules, i.e. |A| = |stat A | + |rul A |. We also sometimes use the notation A[init=I] (resp. A[fin=I]) for the automaton obtained from A by setting its initial (resp. final) states to I.

Let eve(w) = {0} ∪ dom(w) be the set of all positions of w and the start event 0. A run of A on a word w is a function r : eve(w) → stat A so that r(0) ∈ init A and r(π-1)

ǫ * → a → ǫ *
→ r(π) is justified by rul for all π ∈ dom(w) with a = lab w (π). A run is successful if r(|w|) ∈ fin A . The language L(A) ⊆ Σ * is the set of all words that permit a successful run by A.

An nfa is called productive, if all its states are used in some successful run. This is the case if all states are reachable from some initial state, and if for all states, some final state can be reached.

An nfa A is deterministic or a dfa if it has at most one initial state, no epsilon rules, and for every pair (q, a) there exists at most one rule q a → q ′ ∈ rul A . Note that for every word w there exists at most one run by a dfa A.

The ambiguity amb A (w) is the number of successful runs of A on w. This measures the degree of non-determinism of nfas A. Clearly, amb A (w) ≤ 1 for all w ∈ Σ * if A is a dfa. Let N be the set of natural numbers and N 0 the set of non-negative integers. Given k ∈ N, we call the ambiguity of A k-bounded if amb A (w) ≤ k for all w ∈ Σ * . It is bounded, if it is bounded by some k.

Theorem 1 (Stearns and Hunt 85, Weber and Seidl 86). For nfas bounded ambiguity and k-bounded ambiguity with fixed k can be decided in P-time.

Decidability of k-bounded ambiguity for fixed k is shown by Theorem 4.1 of Stearns and Hunt [START_REF] Stearns | On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata[END_REF]. They don't report the precise polynomial though. The result on bounded ambiguity was shown by Weber and Seidl [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF]. Here we can obtain a decent polynomial as follows. They define p w → q by A if there exists a run of A[init={p}] on w that ends in q and show that an nfa A has unbounded ambiguity iff there exists a word w ∈ Σ + and distinct states p = q such that p w → p, p w → q, and q w → q by A. This can be tested in O(|A| 3 ) as shown very recently by [START_REF] Allauzen | General algorithms for testing the ambiguity of finite automata[END_REF].

In the case of words, we will see that we can reduce (k)-bounded delay and concurrency of queries defined by dfas to (k)-bounded ambiguity of nfas.

Bounded Valuedness of Tree Transducers

In a first step, we generalize the results on bounded ambiguity to standard tree automata for binary trees [START_REF] Hubert Comon | Tree automata techniques and applications[END_REF], and in a second to bounded valuedness of tree transducers.

Let Σ r = Σ 0 ⊎ Σ 2 be a ranked alphabet with constants in Σ 0 and binary function symbols in Σ 2 . The set of binary trees T bin Σr is the least set of unranked trees over Σ r that contains all constants c ∈ Σ 0 and pairs f (t 1 , t 2 ) where f ∈ Σ 2 and t 1 , t 2 ∈ T bin Σr . The nodes of a ranked tree t are defined by: nod (c) = {ǫ} and nod (f (t

1 , t 2 )) = {ǫ} ∪ {1•π | π ∈ nod (t 1 )} ∪ {2•π | π ∈ nod (t 2 )}.
A tree automaton (nta) with signature Σ r is a tuple of three finite sets A = (stat, fin, rul ) such that fin ⊆ stat and rul ⊆ ∪ i∈{0,2} stat i+1 × Σ i . We denote rules in rul as f (q 1 , q 2 ) → q and c → q where q 1 , q 2 , q ∈ stat, f ∈ Σ 2 and c ∈ Σ 0 . A run of A on a tree t ∈ T bin Σr is a function r : nod (t) → stat mapping nodes to states, such that for all π ∈ nod (t), if

lab t (π) = f ∈ Σ 2 then rule f (r(π•1), r(π•2)) → r(π) belongs to rul , and if lab t (π) = c ∈ Σ 0 then rule c → r(π) belongs to rul . A run r is successful if r(ǫ) ∈ fin. Automaton A recognizes the language of binary trees L bin (A) ⊆ T bin
Σr that permit a successful run by A.

An nta is called bottom-up deterministic or a dta if no two of its rules have the same left-hand side. We call it top-down deterministic or a d ↓ nta if the set of final states fin contains at most one element, and if for every f ∈ Σ 2 and state q ∈ stat there is at most one rule matching f (q 1 , q 2 ) → q in rul .

The ambiguity amb A (t) is the number of successful runs of A on t. Clearly, amb A (t) ≤ 1 for all t ∈ T bin Σr if A is bottom-up or top-down deterministic. Bounded and k-bounded ambiguity of ntas are defined as for dfas, and were proved to be decidable in P-time by Seidl in [START_REF] Seidl | On the finite degree of ambiguity of finite tree automata[END_REF] and [START_REF] Seidl | Deciding equivalence of finite tree automata[END_REF] respectively (for fixed k).

Theorem 2 (Seidl 89). Bounded ambiguity and k-bounded ambiguity for fixed k of tree automata on ranked trees (ntas) in P-time.

These results for trees generalize those for words in a straightforward manner. However we don't know, in the case of trees, how to reduce (k)-bounded delay and concurrency of queries defined by dtas to (k)-bounded ambiguity of ntas. Instead, we will need even stronger results on bounded valuedness of tree transducers.

Given a binary relation R ⊆ S × S ′ and an element s ∈ S, let #R(s) be the number of s ′ ∈ S ′ such that (s, s ′ ) ∈ R. The valuedness of R is the maximal such number val (R) = max s∈S #R(s). We call R k-bounded if val (R) ≤ k, and bounded if it is k-bounded for some k ∈ N 0 .

Let Σ r = Σ 2 ∪ Σ 0 and ∆ r = ∆ 2 ∪ ∆ 0 be binary signatures. A bottom-up tree transducer with input signature Σ r and output signature ∆ r is a triple T = (stat, fin, rul ) that consists of a finite set of states stat, a subset of final state fin ⊆ stat, and a finite set of rules rul of the following forms:

f (q 1 (x 1 ), q 2 (x 2 )) → q(g(x 1 , x 2 )) or a → q(b)
where x 1 , x 2 are two fixed variables, q 1 , q 2 , q ∈ stat, a ∈ Σ 0 , f ∈ Σ 2 , b ∈ ∆ 0 and g ∈ ∆ 2 . Note that tree transducers usually admit more general rules [START_REF] Seidl | Single-valuedness of tree transducers is decidable in polynomial time[END_REF], but these simpler rules suffice for our usage of tree transducers. The size of T is the sum of the numbers of its rules and states. Its semantics is a binary relation T ⊆ T bin Σr × T bin ∆r defined in the obvious manner. Theorem 3 (Seidl 92). Bounded valuedness of relations T between ranked trees defined by bottom-up tree transducers T can be decided in P-time in the size of T . This result was proved by Seidl in [START_REF] Seidl | Single-valuedness of tree transducers is decidable in polynomial time[END_REF]. Note that it is not known for fixed k whether k-valuedness can be decided in P-time. The best existing algorithm is in coNP-time (Theorem 2.2 of [START_REF] Seidl | Equivalence of finite-valued tree transducers is decidable[END_REF]).

Note also that every dta A can be mapped to some bottom-up tree transducer T in linear time, such that T relates trees t ∈ L bin (A) to successful runs by A on t. It then holds that T is k-valued if and only if A is k-unambiguous. This shows that deciding k-ambiguity of ntas can be reduced to k-valuedness of bottom-up tree transducers, but not necessarily vice versa.

Translation to Unranked Trees

Since dealing with Xml we are mostly interested in unranked trees. We will use the top-down encoding that is also called first-child next-sibling encoding [START_REF] Koch | Efficient processing of expressive node-selecting queries on xml data in secondary storage: A tree automata-based approach[END_REF] or Rabin's encoding [START_REF] Rabin | Decidability of Second-Order Theories and Automata on Infinite Trees[END_REF] in order to lift boundedness results from ranked to unranked trees. In the appendix, we will also use a bottom-up encoding called Currying [START_REF] Carme | Querying unranked trees with stepwise tree automata[END_REF], in order to illustrate the generality of our results.

We define the set T Σ of unranked trees over Σ to be the least set that contains all pairs a(t 1 , . . . , t m ) consisting of a letter a ∈ Σ and a tuple (t 1 , . . . , t m ) of unranked trees in T Σ where m ≥ 0. Clearly, T bin Σr ⊆ T Σr for every binary signature Σ r .

Given an unranked alphabet Σ, let Σ ⊥ = Σ ⊎ {⊥} be the ranked alphabet where all symbols of Σ are binary and ⊥ is the unique constant. The encoding is defined by a function fcns : T Σ → T bin Σ ⊥ is illustrated in Figure 1(b). nta A over Σ ⊥ defines a language of unranked trees modulo the fcns encoding L(A) = {t ∈ T Σ | fcns(t) ∈ L bin (A)}.

Queries and Canonical Languages

We abstract databases into relational structures in order to reason about words and trees in a common framework. In particular, we recall the notion of canonical languages for n-ary queries, first-order queries, and n-ary queries in words and trees.

Queries for Relational Structures

We define queries for relational structures by canonical languages of annotated relational structures. In the case of words and trees, this will enable definitions of queries by deterministic finite automata.

A relational signature ∆ consists of a finite set of relation symbols r ∈ ∆ each with a fixed arity ar(r) ∈ N 0 . A relational structure s over ∆ consists of a nonempty finite set dom(s) called the domain of s and relations r s ⊆ dom(s) ar(r) interpreting all symbols r ∈ ∆. We write S ∆ for the set of structures over ∆. Definition 1. Let ∆ be a relational signature and n ∈ N 0 . A schema over ∆ is a subset S ⊆ S ∆ . An n-ary query with schema S is a function Q with domain dom(Q) = S, which maps all structures s ∈ S to a set of tuples of elements Q(s) ⊆ dom(s) n . A Boolean query is a query of arity 0.

Below, we will define queries in words, where the schema dom(Q) is a class of relational structures of words in Σ * , and queries in unranked trees where the schema is a class of relational structures of unranked trees T Σ . Further restrictions on these domains can be defined by automata or Xml schemas.

Canonical Languages

Boolean queries with domain S ∆ can be identified with schemas L Q = {s | () ∈ Q(s)}. But how can we define languages of structures for more general n-ary queries?

In order to do so, we fix an ordered set of distinct variables V n = {x 1 , . . . , x n } and define extended relation signatures ∆ n = ∆ ∪ V n such that every variable becomes a monadic relation symbol. For every structure s ∈ S ∆ and tuple τ = (π 1 , . . . , π n ) ∈ dom(s) n we define an annotated structure s * τ ∈ S ∆n as follows:

dom(s * τ ) = dom(s)

r s * τ = r s for all r ∈ ∆ x s * τ i = {π i } for all 1 ≤ i ≤ n
We call a structure s ∈ S ∆n canonical if x s is a singleton for all x ∈ V n . Clearly, all annotated structures s * τ are canonical. Conversely, every canonical structure s is equal to some annotated structure s * τ . We therefore define the canonical language of n-ary queries as follows:

Definition 2. The canonical language L Q of an n-ary query Q is the following set of annotated structures:

L Q = {s * τ | τ ∈ Q(s)}
Note that the canonical language of a Boolean query indeed coincides with the schema L Q = {s | () ∈ Q(s)}. Note however, that the domain of a query is only partially specified by the canonical language. What is missing in the canonical language is the difference between structures s verifying s ∈ dom(Q) and structures s such that Q(s) = ∅. In order to fix this problem, we identify a query Q by the pair (L Q , dom(Q)) of its canonical language and its domain.

First-Order Queries

We define logical operations for n-ary queries Q, Q ′ with the same schema S: conjunction Q ∧ Q ′ , negation ¬Q, existential quantification ∃x i .Q for all 1 ≤ i ≤ n, and cylindrification c θ Q for functions θ : {1, . . . , m} → {1, . . . , m} with {1, . . . , n} ⊆ θ({1, . . . , m}). All these queries have the same domain, say S, and satisfy for all structures s ∈ S:

conjunction Q ∧ Q ′ (s) = Q(s) ∩ Q ′ (s) negation ¬Q(s) = dom(s) n -Q(s) quantification ∃x i .Q(s) = {(π 1 , . . . , π i-1 , π i+1 , . . . , π n ) | ∃π i . (π 1 , . . . , π n )∈Q(s)} cylindrification c θ Q(s) = {(π θ(1) , . . . , π θ(m) ) ∈ dom(s) m | (π 1 , . . . , π n ) ∈ Q(s)}
Note that ∃x i .Q is a query of arity n-1, and c θ Q of arity m ≥ n, while all others have arity n. While projection deletes component in all tuples, cylindrification permits extension by new components, plus copying and permutation, but no deletion.

We next define formulas of first-order logics over a relational signature ∆ as usual, where y ranges of an infinite vocabulary of variables V, r ∈ ∆, and m = ar(r):

φ ::= r(y 1 , . . . , y m ) | φ 1 ∧ φ 2 | ¬φ | ∃y.φ
Every fo formula φ with at most m free variables ỹ = (y 1 , . . . , y m ) ∈ V m defines an m-ary query Q φ(ỹ) whose domain contains all ∆-structures.

Q φ1∧φ2(ỹ) = Q φ1(ỹ) ∧ Q φ2(ỹ) Q ¬φ(ỹ) = ¬Q φ(ỹ) Q (∃z.φ)(ỹ) = ∃z.Q φ(ỹ,z)
Q r(y1,...,yn)(y θ(1) ,...,y θ(m) ) = c θ r

Here, we identify relation symbol r with the query of arity ar(r) that satisfies r(s) = r s for all structures s ∈ S.

Queries on Words

Non-empty words over a finite alphabet Σ can be identified with relational structures. We write w•w ′ ∈ Σ * for the concatenation of two words w, w ′ ∈ Σ * , and ǫ ∈ Σ * for the empty word. The domain of the structure of a word w = a 1 • . . . •a m is the set of its positions:

dom(w) = pos(w) = {1, . . . , m}
Note that the domain of all non-empty words is non-empty. Indeed, we define structures only for non-empty words in Σ + in order to avoid anomalies later on.

The structure of a word w ∈ Σ + has signature ∆ = {lab a | a ∈ Σ} ∪ {≤} with the following interpretations where w = a 1 • . . . •a m :

lab w a = {i | a i = a, 1 ≤ i ≤ m} ≤ w = {(i, j) | 1 ≤ i ≤ j ≤ m}
An n-ary query Q in words has some schema dom(Q) ⊆ Σ + and selects n-tuples of positions in words in dom(Q). Suppose that we fix dom(Q) = Σ + . We can then define a monadic query by the following fo formula with a single free variable x 1 :

φ(x 1 ) = df ∃x 2 (x 1 ≤ x 2 ∧ lab a (x 2 ))
For every word w in the schema, the query Q φ(x1) defined by this formula selects all positions before some a-labeled positions. Given a word w = a 1 • . . . •a m ∈ Σ * and a tuple τ = (π 1 , . . . , π n ) ∈ dom(w) n , we can identify the annotated structure w * τ with the following annotated word over Σ × 2 Vn : (a 1 ,

{x i | π i = 1})• . . . •(a m , {x i | π i = m})
For instance we identify (a•a•b) * (2, 1) with the word (a, {x 2 })•(a, {x 1 })•(b, ∅).

The canonical language of an n-ary query Q in words over ∆ thus can be identified with a language L Q of annotated words with alphabet Σ × 2 Vn .

Queries on Unranked Trees

We can identify unranked trees in T Σ with structures over the relational signature ∆ = {lab a | a ∈ Σ} ∪ {ch * , ns * }, where all labeling relations are monadic and all others binary. The domain of the structure of t = b(t 1 , . . . , t m ) ∈ T Σ is the set of its nodes:

dom(t) = nod (t) = {ǫ} ∪ {i•π | π ∈ nod (t i )}
The relations of the structure of t are defined as follows where a ∈ Σ:

lab t a = {ǫ | a = b} ∪ {i•π | π ∈ lab ti a , 1 ≤ i ≤ m} (ch * ) t = {(π, π•π ′ ) | π•π ′ ∈ nod (t)} (ns * ) t = {(π•i, π•j) | 1 ≤ i ≤ j, π•j ∈ nod (t)} ∪ {(ǫ, ǫ)} The word w = a•b•a•c•a, for instance, can be encoded by the tree t = d(a, b, a, c, a), where d ∈ Σ is an arbitrary symbol. Note that nod (t) = {ǫ} ∪ dom(w).
Queries Q in unranked trees of T Σ are queries with some domain dom(Q) ⊆ T Σ . They select tuples of nodes Q(t) ⊆ nod (t) n for all trees t ∈ dom(Q). For instance, if we fix the schema to T Σ then we can define a query for all trees that selects all nodes with a-labeled descendants by the following fo formula with one free variable x 1 :

φ(x 1 ) = df ∃x 2 (ch * (x 1 , x 2 ) ∧ lab a (x 2 ))
In analogy to the case of words, the canonical language of an n-ary query Q in unranked trees over Σ can be identified with a language of unranked trees over the alphabet Σ × 2 Vn where V n = {x 1 , . . . , x n }.

Streaming Algorithms for Query Answering

We discuss fundamental concepts of streaming algorithms for query answering. In particular, we introduce the notion of bounded delay and bounded concurrency and discuss their relevance for streamability.

Linearizations of Structures

A streaming algorithm that answers a query Q in some class of structures S reads a linearization of a structure s ∈ S from the input stream, and computes a collection of answers Q(s) incrementally.

Since words are linear structures, they can be put onto a stream in the naive manner. A streaming algorithm for words in Σ + can be understood as a oneway automaton, that reads the letters of a word w ∈ Σ + from the left to the right. It assigns states to all events eve(w) = {0} ∪ dom(w), i.e., to all positions of w and to the start event 0. The set of events is totally ordered with least element 0. We write dom η (w) = {1, . . . , η} for the set of positions of w visited before the event η.

Unranked trees need linearization in order to be put onto a stream. For every set Set, we define a set of tagged opening and closing parenthesis:

Set = {op, cl} × Set
An opening parenthesis (op, a) corresponds to the Xml tag <a> and a closing parenthesis (cl, a) to the Xml tag </a>. For every tree t ∈ T Σ we define the nested word nw(t) ∈ Σ by linearization as follows:

nw(a(t 1 , . . . , t n )) = (op, a)•nw(t 1 )• . . . •nw(t n )•(cl, a)
This word is well-nested in that every opening parenthesis is properly closed.

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)
. The events of the nested word nw(t) can be identified with element of the following set:

eve(t) = {start} ∪ nod (t)
Let ≤ be the total order on eve(t) corresponding to the total order of eve(nw(t)) and pred (e) ∈ eve(t) be the immediate predecessor of an event η ∈ nod (t). For instance, pred (op, 2•1) = (cl, 1) for the tree t = a(b, c(d), f ). We write dom η (t) = {π ∈ nod (t) | (op, π) ≤ η} for the set of all nodes visited until event η.

Earliest Selection and Bounded Delay

The delay of a query is the maximal life time of some query answer. In order to define the delay formally, we must say what it means that an event is sufficient for the selection of an answer candidate, or equivalently, we must define the earliest event that is sufficient for its selection.

We consider the cases of words and trees in simultaneously, where either S = Σ * is the set of all words or S = T Σ the set of all unranked tree over Σ. Let Q be an n-ary query in S, s ∈ S a structure, and η ∈ eve(s) an event of s. A complete candidate until event η is a tuple τ ∈ dom η (s) n . Given two structures s 1 , s 2 ∈ S and an event η ∈ eve(s 1 ) ∪ eve(s 2 ), we say that the prefixes of the linearizations of s 1 and s 2 until η coincide, if:

eq η (s 1 , s 2 ) ⇔ dom η (s 1 ) = dom η (s 2 ) ∧ ∀a ∈ Σ. ∀π ∈ dom η (s 1 ). (lab s1 a (π) ⇔ lab s2 a (π))
Definition 3. We call an event η sufficient for selection of a complete candidate τ until η in structure s by query Q, and write (τ, η) ∈ sel Q (s), if τ will be selected by Q in all possible continuations of the stream beyond η:

(τ, η) ∈ sel Q (s) ⇔ τ ∈ dom η (s) n ∧ ∀s ′ ∈ dom(Q). eq η (s, s ′ ) ⇒ τ ∈ Q(s ′ )
Note that allowed continuations are only those that extend the current prefix of the linearization of the structure to a member of dom(Q). Note also that the start event may be sufficient to select the empty tuple () in Boolean queries where n = 0, while it is never sufficient for selection if n ≥ 1 since otherwise

τ ∈ dom η (s) n . Let latest((π 1 , . . . , π n )) = min{η ∈ eve(s) | π 1 , . . . , π n ∈ dom η (s)}
be the minimal event, where all elements of the tuple have been visited. The delay of an n-ary query Q for a tuple τ ∈ dom(s) is the number of events η following latest(τ ) such that η is insufficient for selection, i.e. (τ, η) ∈ sel Q (s).

delay Q (s, τ ) = |{η ∈ eve(s) | latest(τ ) ≤ η, (τ, η) ∈ sel Q (s)}| A query Q has k-bounded delay if delay Q (s, τ ) ≤ k for all s ∈ dom(Q) and τ ∈ Q(s). It has bounded delay if it has k-bounded delay for some k ≥ 0.
Having bounded delay means that every Eqa algorithm will output selected tuples a constant time after completion. This is a guarantee on the quality of service.

Earliest Rejection and Bounded Concurrency

The concurrency of a query is the maximal number of concurrently alive answer candidates at every time point [START_REF] Bar-Yossef | Buffering in query evaluation over XML streams[END_REF]. In order to define the concurrency formally, we have to define aliveness of answer candidates. Intuitively, a candidate is alive at an event at which it can neither be safely rejected nor selected.

Recall that the concepts of earliest selection and rejection are closely related to the idea of Eqa. An Eqa algorithm for a query Q is a streaming algorithm that inputs a linearization of a structure on the stream, and decides selection and rejection of answer candidates at every time point (without knowing the rest of the stream). This way, it needs to keep in main memory only alive candidates, which are neither safe for selection nor rejection. As an example, consider the monadic query Q 2 that selects all positions in words w ∈ {a, b, c} * that are labeled by a and followed by b•b. When applied to 2), (5)}. A streaming algorithm can enumerate these answers by using a sliding window of length 3. Position 1 for instance can be rejected when having seen the labels of positions 1 and 2, while position 2 can be selected when having seen the labels of positions 2, 3, and 4.

w 2 = a•a•b•b•a•b•b•c•a•b•a•b, this query returns Q 2 (w 2 ) = {(
In order to formalize the concept of earliest rejection for n-ary queries, we have to deal with partial answer candidates for a given structure s. We fix a constant • that represents unknown components, and define partial tuples τ of positions until η ∈ eve(s) as members of (dom η (s) ⊎ {•}) n . So far, we have only studied complete answer candidates, which do not contain any unknown component. We write compl (τ, s, η) for the set of complete candidates, in which all unknown components of τ have been instantiated with elements π ∈ dom(s)dom η (s). Definition 4. We call a partial candidate τ rejected at event η ∈ eve(s), if no completion of τ by nodes in the future of η can be selected by Q.

(τ, η) ∈ rej Q (s) ⇔ τ ∈ (dom η (s) ⊎ {•}) n ∧ ∀s ′ ∈ dom(Q). eq η (s, s ′ ) ⇒ ∀τ ′ ∈ compl(τ, s ′ , η). τ ′ / ∈ Q(s ′ )
We call a partial candidate τ ∈ (dom η (s)∪{•}) n alive at η if τ is neither rejected nor selected at η.

(τ, η) ∈ alive Q (s) ⇔ τ ∈ (dom η (s) ∪ {•}) n and (τ, η) ∈ rej Q (s) and (τ, η) ∈ sel Q (s)
The concurrency of a query Q on a structure s ∈ dom(Q) at event η ∈ eve(s) is the number of alive partial candidates τ until η, so that η is neither sufficient for selection or rejection of τ .

concur Q (s, η) = |{τ ∈ (dom η (s) ∪ {•}) n | (τ, η) ∈ alive Q (s)}|
We choose to include the empty tuple • n in the concurrency, because in our algorithm it is processed like any other partial tuple 4 . Hence Boolean queries have concurrency at most 1, and for monadic queries it is at most |dom(s)| + 1. Concurrency 0 means that the query is empty.

Lemma 5. For all monadic queries Q, structures s ∈ dom(Q), and events η ∈ eve(s):

concur Q (s, η) ≤ sup s ′ ∈dom(Q),τ ∈Q(s ′ ) delay Q (s ′ , τ ) + 1
The lemma fails for queries of higher arities, where the delay between the tuple components may be unbounded even though the delay of selection of complete tuples is bounded. In this case, the set of alive partial tuples may grow without bound, even though the set of alive complete tuples is bounded. For instance consider the query Q with Q(t) = nod (t) 2 for all trees t ∈ T Σ . This query has delay 0, since every pair of nodes can be selected immediately, once its last component has been visited. Nevertheless, all partial tuples (π, •) with π ∈ dom η (t) are alive at all events η, so that the concurrency of this query is not bounded.

Proof. Let s ′ ∈ S and k ∈ N 0 ∪ {∞}. In the case of words (where S = Σ * ), we define dom k η (s ′ ) by {π ′ | ηk ≤ π ′ ≤ η}, and in the case of trees (where

S = T Σ ), we define dom k η (s ′ ) as {π ′ | pred k (η) ≤ (op, π ′ ) ≤ η}. Let Q be a monadic query. Let d = sup s ′ ∈dom(Q),τ ∈Q(s ′ ) delay Q (s ′ , τ
) be the number in the lemma, and s ∈ dom(Q) be a structure with event η ∈ eve(s). We claim for all π ∈ dom(s) that:

π ∈ dom d η (s) ⇒ ((π), η) ∈ alive Q (s)
To see this, we first note that if π ∈ dom η (s) then π is not alive at η. Now let us consider π ∈ dom η (s)dom d η (s). We distinguish two cases. 1. In the first case, there exists a continuation

s ′ ∈ dom(Q) with eq η (s, s ′ ) such that (π) ∈ Q(s ′ ). This continuation s ′ satisfies delay Q (s ′ , (π)) ≤ d, so that π ∈ dom η (s) -dom d η (s) yields ((π), η) ∈ sel(s)
. This contradicts aliveness.

2. Otherwise, all continuations s ′ of s beyond η satisfy (π) ∈ Q(s ′ ), so that ((π), η) ∈ rej(s). This equally implies non-aliveness.

This proves the claim, which yields for all partial tuples τ :

(τ, η) ∈ alive Q (s) ⇒ τ ∈ dom d η (s) ∪ {•} Hence, concur Q (s, η) ≤ d + 1 by definition of concurrency.
We say that the concurrency of a query Q is bounded if there exists k ≥ 0 such that concur Q (s, η) ≤ k for all structures s ∈ dom(Q) and η ∈ eve(s). Note that queries with unbounded concurrency cannot be processed in streaming manner with bounded memory. Proposition 6. A monadic query with k-bounded delay has (k+1)-bounded concurrency.

Proof. This is an immediate consequence of Lemma 5.

The converse does not hold. As a counter example, consider the monadic query which selects the first letter of all words whose last letter is a b. This query has concurrency bounded by 1, since the first letter is the only alive candidate before the end, but unbounded delay.

Schema Elimination

Domain restrictions of queries by schemas are relevant to Eqa, since they constrain the possible continuations of a stream. As an example, reconsider the monadic query Q 2 that selects all positions in words w that are labeled by a and followed by b•b, but now with domain restricted by schema (a|b

) * •c•(a•b) * .
If the word w on the stream is assumed to satisfy the schema, then no position that follows a c symbol on the stream can be selected.

Eqa for queries Q with schema restriction can be reduced to Eqa for queries without. In order to do so, we define a query

σ Q with dom(σ Q ) = S such that sel Q = sel σQ . We set σ Q (s) = Q(s) if s ∈ dom(Q) and dom(s) n otherwise.
Similarly for rejection, we define a query

ρ Q with dom(ρ Q ) = S by ρ Q (s) = Q(s) if s ∈ dom(Q) and ∅ otherwise. Lemma 7. sel Q = sel σQ and rej Q = rej ρQ . Proof. Straightforward from the definitions. Let τ ∈ dom η (s) n : (τ, η) ∈ sel σQ iff τ ∈ dom η (s) n ∧ ∀s ′ ∈ S. eq η (s, s ′ ) ⇒ τ ∈ σ Q (s ′ ) iff τ ∈ dom η (s) n ∧ ∀s ′ ∈ dom(Q). eq η (s, s ′ ) ⇒ τ ∈ Q(s ′ ) (τ, η) ∈ rej ρQ iff τ ∈ (dom η (s) ∪ {•}) n ∧ ∀s ′ ∈ S. eq η (s, s ′ ) ⇒ ∀τ ′ ∈ compl (τ, s ′ , η). τ ′ ∈ ρ Q (s ′ ) iff τ ∈ (dom η (s) ∪ {•}) n ∧ ∀s ′ ∈ dom(Q). eq η (s, s ′ ) ⇒ ∀τ ′ ∈compl (τ, s ′ , η). τ ′ ∈ Q(s ′ )
However, given automata A and B with L(A) = L(Q) and L(B) = S, we cannot build an automaton recognizing σ Q or ρ Q without a blowup in O(2 n ) in the general case, since we have to extend the alphabet of B from Σ to Σ × 2 Vn .

Bounded Delay and Concurrency for Word Automata

We consider the case, where queries in words are defined by two deterministic finite automata, that recognize the canonical language of the query and its schema respectively. We obtain P-time decision procedures for bounded delay and concurrency by reduction to bounded ambiguity of non-deterministic finite automata.

Defining n-ary Queries

We can define queries by two automata, one for the canonical language and another for the schema. We call an nfa canonical if and only if its language is. Definition 8. Let A be a canonical nfa with alphabet Σ × 2 Vn and B an nfa with alphabet Σ, such that w ∈ L(B) for all w * τ ∈ L(A). The query Q (A,B) defined by the pair (A, B) is the unique n-ary query with domain L(B) and canonical language L(A).

If L(B) = Σ + then we write Q A instead of Q (A,B) .
Automaton B is needed in order to distinguish those words on which the query is not defined from those where the query returns the empty set. Note that if

Q (A,B) (w) = ∅ then w ∈ L(B).
Let the type of a word w with alphabet Σ×2 Vn be a function type w : V n → N 0 that counts how many times a variable appears in labels, i.e., for x ∈ V n :

type w (x) = |{π ∈ dom(w) | lab w (a,V ) (π) with x ∈ V }|
We say that a word w has type 1

(x) = type w1•w (x) = 1 for all x ∈ V n
We can thus define the type of a state q of a productive canonical nfa in a unique manner, via the type of some word w that evaluates to this state. type(q) will denote this type. Furthermore, as the automaton is canonical and productive, this type is determined by the set {x ∈ V n | type w (x) = 1}. So we can identify the type of a state with a subset of V n .

Reconsider the query Q φ(x1) in words with alphabet {a, b} from Section 3.4, which selects all positions labeled by a or eventually succeeded by an a. In Figure 2, we illustrate an automaton for the canonical language of this query graphically. Its states have the following types: ∅ for q 0 (no variables seen before entering in this state), and {x 1 } for q 1 and q 2 (x 1 seen before entering in these states).

Query answering for dfas is the algorithmic problem that receives as input two dfas A and B defining an n-ary query and a word w ∈ L(B) defining a valid

q 0 q 1 q 2 (a, {x 1 }) (b, {x 1 }) (a, ∅) (a, ∅) (b, ∅) (b, ∅) (a, ∅) (b, ∅) Figure 2: A dfa for the canonical language of Q φ(x 1 ) where φ = ∃x 2 . (x 1 ≤ x 2 ∧ laba(x 2 )).
database, and returns as output Q (A,B) (w). The objective is to find all tuples τ of positions in w such that w * τ ∈ L(A). The naive algorithm enumerates all tuples τ ∈ dom(w) n and runs A deterministically on w * τ . This algorithm first resolves the choice of τ non-deterministically, before running the deterministic automaton A.

Determinism for canonical automata will turn out to be essential for Ptime streaming algorithms and decision complexity (e.g. the safety property below). It should be noticed that canonical nfas can always be determinized without changing the query they define. This would fail when defining queries by selection automata, i.e. nfas over Σ with a set of selection states as considered in [START_REF] Frick | Query evaluation on compressed trees[END_REF][START_REF] Niehren | N-ary queries by tree automata[END_REF].

Computing Delays of Queries

We show how to decide whether a query has bounded delay and how to compute this delay in polynomial time. We consider the case with schemas, since subsequent schema elimination as proposed in Section 4.4 would yield polynomial bounds only for queries with fixed arity n. Moreover, these bounds for fixed n would be larger than those obtained by the following construction.

For every language L ⊆ Σ + we define a language of annotated words L ⊗ ∅ with alphabet Σ × 2 Vn such that all letters of words in L are annotated by

∅, i.e., L ⊗ ∅ = {(a 1 , ∅)• . . . •(a k , ∅) | a 1 • . . . •a k ∈ L} Definition 10. If dfas A and B define a query then we call a state (p, q) ∈ stat A ×stat B safe for selection by Q (A,B) if L(B[init={q}])⊗∅ ⊆ L(A[init={p}]).
Figure 3 illustrates an automaton for the query that selects all a-nodes that are succeeded by b•b. In this example, we assume the universal schema B with a single state, so that A is isomorphic to P(A, B). The types and safety properties of all states are indicated in the figure .  We next show that safe states capture sufficiency for selection. In order to do so, we construct a dfa P(A, B) which runs A and B in parallel. Its alphabet is Σ × 2 Vn as for A, while B has alphabet Σ.

stat P(A,B) = stat A × stat B init P(A,B) = init A × init B fin P(A,B) = fin A × fin B p (a,V ) → p ′ ∈ rul A q a → q ′ ∈ rul B (p, q) (a,V ) → (p ′ , q ′ ) ∈ rul P(A,B) p 0 p 1 p 2 p 3 (a, ∅) (b, ∅) (a, {x 1 }) (b, ∅) (b, ∅) (a, ∅) (b, ∅) unsafe sel unsafe sel unsafe sel safe sel ∅ {x 1 } {x 1 } {x 1 }
} = V 1 ,
∈ sel Q (A,B) (w). Proof. Sufficiency for selection (τ, η) ∈ sel Q (A,B) (w) is equivalent to τ ∈ dom η (w) n and ∀w ′ ∈ L(B) : eq η (w, w ′ ) ⇒ w ′ * τ ∈ L(A). Let w = w 0 •w 1 such that |w 0 | = η. Since τ ∈ dom η (w) n , we have w * τ = (w 0 * τ )•(w 1 ⊗ ∅). Furthermore, eq η (w, w ′ ) is equivalent to ∃w ′ 1 . w ′ = w 0 •w ′ 1 . Now r(η)
is the state that the unique run of P(A, B) on w 0 * τ reaches (determinism). For (p, q) = r(η) we have:

∀w ′ ∈ L(B) : eq η (w, w ′ ) ⇒ w ′ * τ ∈ L(A) ⇔ ∀w ′ 1 . w 0 •w ′ 1 ∈ L(B) ⇒ (w 0 * τ )•(w ′ 1 ⊗ ∅) ∈ L(A) ⇔ ∀w ′ 1 . w ′ 1 ∈ L(B[init = {q}]) ⇒ w ′ 1 ⊗ ∅ ∈ L(A[init = {p}]) (determinism) ⇔ L(B[init = {q}]) ⊗ ∅ ⊆ L(A[init = {p}]) ⇔ r(η) safe for selection by Q (A,B)
Conversely, assume that r(η) = (p, q) is safe for selection by Q (A,B) . Since we assumed A and B to be productive, this implies that type(p) = V n , so that τ ∈ dom η (w) n . We can thus decompose w = w 0 •w 1 such that |w 0 | = η as above, and apply the above equivalence, in order to conclude from safety for selection, that ∀w ′ ∈ L(B) : eq η (w, w ′ ) ⇒ w ′ * τ ∈ L(A), and thus sufficiency for selection.

The parallel automaton P(A, B) is canonical, since L(A) = L(P(A, B)), but may contain non-productive states, even if A and B are productive. For instance, consider productive automata A and B that define the query Q with dom(Q) = {a, a•a}, Q(a) = {1} and Q(a•a) = ∅. We will be interested only in the productive part of the canonical automaton P(A, B), for which unique types exist. Proof. To see this, suppose that (p, q) is safe and reachable. Since B is productive, there exists a word w ∈ L(B[init={q}]). Safety proves that w ⊗ ∅ ∈ L(A[init = {p}]). Thus, w ∈ P(A, B)[init = {(p, q)}], so that (p, q) is productive. Since A is canonical, P(A, B) is canonical, so that type(p) ⊎ type(w ⊗ ∅) = V n .

Proposition 13. Let Q (A,B) be defined by productive dfas A and B, and let P u be the restriction of nfa P(A, B) to productive unsafe states of type V n .

1. The delay of Q (A,B) is bounded if and only if the digraph of nfa P u is acyclic. 2. In this case, the delay of Q (A,B) is equal to the length of the longest path in P u .

Proof. Let P = P(A, B) and P u the restriction of P to productive unsafe states of type V n . Let q be a state of P u for which a cycle exists. Since all states of P u are productive in P, there exists a word v 1 ∈ L(P[fin = {q}]). Since P u has a cycle, there exists a nonempty word v 2 ∈ L(P[init = {q}, fin = {q}]). Again, since P is productive, there exists a word

v 3 ∈ L(P[init = {q}]). It follows for all m ≥ 0, that v = v 1 •(v 2 ) m •v 3 ∈ L(P). Since L(P) = L(A)
, word v has the form w * τ for some word w ∈ Σ * and τ ∈ dom(w) n . By Lemma 11, none of the events in |v 2 | m is sufficient for the selection of τ in w since the run of P on v maps all of them to unsafe states. This shows that the selection delay of τ in v is at least m and thus unbounded.

For the converse, we suppose that P u is acyclic and show that the delay of Q (A,B) is bounded by the length of the longest path in stat P u . Let w and τ be such that w * τ ∈ L(A) and r be the successful run of A that accepts this word. Let η be an arbitrary event that contributes to the delay of τ , i.e., an event with τ ∈ dom η (w) and (τ, η) / ∈ sel Q (A,B) (w). The first condition yields that type(r(η)) = 1 Vn and the second condition that r(η) is unsafe for selection by Lemma 11. Thus, r(η) ∈ stat P u . Since P u is acyclic, it follows that states r(η) are distinct for distinct events η that contribute to the delay. Furthermore, all these states belong to the same path of P u , such that delay Q (A,B) (w, τ ) is bounded by the length of the longest path in P u .

If P u is acyclic, let r a longest path in P u and let w a word such that w * ∅ labels r. Since all states of P are reachable and productive, there exists w 1 * τ which reaches in P the first state of r; similarly, there exists a word w 2 such that w 2 * ∅ labels a path from the last state of r to a final state of P. Then delay Q (w 1 •w•w 2 , τ ) is the length (here, the number of states) of r.

Hence we get a first algorithm for determining the delay. The remaining question is the complexity of this computation. To obtain an efficient algorithm, we rely on the following characterization of unsafe states. Lemma 14. Let A, B be productive dfas that define a query. A reachable state (p 0 , q 0 ) of P(A, B) is unsafe for selection by Q (A,B) if and only a state (p, q) can be reached from (p 0 , q 0 ) such that: ( U1) either p / ∈ fin A and q ∈ fin B , ( U2) or there exists a transition q a → q ′ ∈ rul B but no transition p (a,∅)

→ p ′ ∈ rul A for all p ′ ∈ stat A .
Proof. Let P = P(A, B). We start with a claim about propagation of unsafety.

Claim 15. Reachable states of P that can reach unsafe states are unsafe.

To see this, let (p 1 , q 1 ) be a reachable state and (p 2 , q 2 ) be an unsafe state that is reached from (p 1 , q 1 ) by some word v 1 , i.e. v 1 ∈ P[init = {(p 1 , q 1 )}, fin = {(p 2 , q 2 )}]. Since (p 2 , q 2 ) is unsafe, there exists a word w ∈ L(B[init

= {q 2 }]) such that w ⊗ ∅ / ∈ L(A[init = {p 2 }]
). We distinguish two cases.

1. If v 1 matches w 1 ⊗ ∅ then w 1 •w ∈ L(B[init = {q 1 }]) and (w 1 •w) ⊗ ∅ / ∈ L(A[init = {p 2 }]), so that (p 1 , q 1 ) is unsafe. 2. If v 1 does not match w 1 ⊗ ∅ then type(p 1 ) = V n so that (p 1 , q 1 )
is unsafe by Lemma 12, since (p 1 , q 1 ) is reachable in P and since A and B are productive.

Based on this claim, we can now show both directions of the lemma.

"⇐" By Claim 15 it is sufficient to show that all states (p, q) satisfying (U1) or (U2) are unsafe. In case of (U1) where p / ∈ fin A and q ∈ fin B , the empty word contradicts the safety of (p, q), since

ǫ ∈ L(B[init = {q}]) but ǫ ⊗ ∅ / ∈ L(A[init = {p}]).
In case of (U2), there exists some transition

q a → q ′ ∈ rul B but no transition p (a,∅) → p ′ ∈ rul A for all p ′ ∈ stat A . Since B is productive, there exists a word w ∈ L(B[init = {q 2 }]). The word a•w now contradicts safety of (p, q) since a•w ∈ L(B[init = {p}]) but (a•w) ⊗ ∅ ∈ L(A[init = {q}]).
"⇒" We show that all unsafe states (p 0 , q 0 ) can reach some state (p, q) that satisfies (U1) or (U2). If (p 0 , q 0 ) is unsafe then there exists a word w ∈ Σ * such that w ∈ L(B[init = {q 0 }]) and w ⊗∅ / ∈ L(A[init = {p 0 }]). Let w 0 be the longest prefix of w such that there exists a run of P[init = {(p 0 , q 0 )}] on w 0 . Let (p, q) be the state reached by this run after reading w 0 , and let w 1 be the suffix of w such that w = w 0 •w 1 . State (p, q) is thus reached from (p 0 , q 0 ). It remains to show that (p, q) satisfies (U1) or (U2).

1. If w 1 = ǫ then p ∈ fin B and q / ∈ fin A , so that (p, q) satisfies (U1).

2. If w 1 matches a•w 2 then there cannot exist any transition p (a,∅)

→ p ′ since w 0 was chosen of maximal length. There exists a transition q a → q ′ for some q ′ though. Hence, (p, q) satisfies (U2).

Lemma 16. The set of reachable safe states for selection for an n-ary query

Q (A,B) can be computed in time O((|Σ| + n) • |A| • |B|) from dfas A and B.
Proof. Instead of the set of reachable safe states, we compute the set of reachable unsafe states. A Datalog program testing the reachability of states satisfying (U1) or (U2), which characterizes unsafety for reachable states by Lemma 14, can be defined as follows: In particular, we can decide in the same time, whether a query Q (A,B) has bounded delay or k-bounded delay, even if k belongs to the input.

p ′ / ∈ fin A q ′ ∈ fin B unsafe sel (p, q). ∀p ′ .p (a,∅) → p ′ / ∈ rul A q a → q ′ ∈ rul B unsafe sel (p, q). (p, q) (a,V ) → (p ′ , q ′ ) ∈ rul P(A,B) unsafe sel (p, q) :-unsafe sel (p ′ , q ′ ). p 0 p 1 p 2 p 3 ok (a, ∅) (b, ∅) (a, {x 1 }) (b, ∅) (b, ∅) (a, ∅) (b, ∅) ǫ ǫ (a, ∅) (b, ∅) unsafe sel unsafe sel unsafe sel {x 1 } {x 1 } {x 1 }
Proof. We first render B productive and construct the dfa P(A, B). Second, we compute all reachable safe states by Lemma 16 and derive the sub-automaton P u , that restricts P(A, B) to productive unsafe states of type V n . By Proposition 13, the delay of Q (A,B) is ∞ if and only if P u contains a cycle. Otherwise, we compute the delay by counting the length of the longest path of P u . All of these operations can be performed in time O((|Σ| + n) • |A| • |B|).

Reduction to Bounded Ambiguity

There exist an alternative method by which to decide bounded delay, which is by reduction to bounded ambiguity of nfas. The interest is more general than the concrete constructions above, in that it can also be applied to bounded concurrency.

The idea is to turn the dfa

P(A, B) it into an nfa D(A, B) such that amb D(A,B) (w * τ ) = delay Q (A,B) (w, τ ) for all τ ∈ Q (A,B) (w).
We construct D(A, B) from P(A, B) by adding a new state ok and ǫ-transitions from all unsafe states of type V n to ok. Figure 4 presents the result of this operation on the automaton in Figure 3.

stat D(A,B) = stat P(A,B) ⊎ {ok}, init D(A,B) = init P(A,B) , fin D(A,B) = {ok} r ∈ rul P(A,B) r ∈ rul D(A,B) unsafe sel (p, q) p has type V n (p, q) ǫ → ok ∈ rul D(A,B) a ∈ Σ ok (a,∅) → ok ∈ rul D(A,B) Proposition 17. For all τ ∈ Q (A,B) (w): delay Q (A,B) (w, τ ) = amb D(A,B) (w * τ ).
Proof. Consider a run r of D(A, B) on a canonical word w * τ with τ ∈ Q(w).

We can show inductively on r that the ambiguity of D(A, B) on w is exactly the number of states used in r that are not safe for selection. The initial state is unique as A is deterministic, so at the beginning the ambiguity is 1. When reading a new letter, if the associated state q is not unsafe or has not type V n , then there is only one way to continue the run, via a rule of P(A, B). If it is unsafe with type V n , then there are two possibilities: either by using the run of P(A, B), or by firing the ǫ-transition. Both runs will succeed (as ok is universal), so in this case the ambiguity is increased by one. Hence amb D(A,B) (w * τ ) is the number of unsafe states used in the run of P(A, B), and also of A, on w * τ .

From the definitions of delay (here the type V n ensures that we start counting at latest(τ )), safe states and by Lemma 11, this is exactly delay

Q (A,B) (w, τ ).
Proposition 17 provides a P-time reduction from bounded delay to bounded ambiguity and from k-bounded delay to k-bounded ambiguity. The results from the literature reported in Theorem 1 thus show that all these problems can be decided in P-time under the assumption that k is fixed.

It should be noticed that Theorem 4 obtained by a direct automaton construction is slightly stronger. First, it allows to compute the optimal bound in P-time, second, does not require to k in order to decide k-boundedness in P-time, and third yields small polynomials.

Deciding Bounded Concurrency

We show how to reduce in P-time bounded concurrency to bounded ambiguity and k-bounded concurrency to k-bounded ambiguity. We notice that we do not know how to obtain any more direct algorithm in this case.

The concurrency of a query counts the number of simultaneously alive partial candidates. In addition to sufficiency for selection, aliveness depends on sufficiency for rejection. We thus need a notion of safe states for rejection. Definition 18. A pair of states (p, q) of P(A, B) is safe for rejection by Q (A,B) if no final state can be reached from (p, q), i.e., if L(P(A, B)[init = {(p, q)}]) = ∅.

We saw in the proof of Theorem 4 how to compute safe states for selection, so now we need a method to compute safe states for rejection.

Lemma 19. The set of safe states for rejection by Q (A,B) for nfas A and B can be computed in time O(|A| • |B|).

Proof. We compute the set of all unsafe states for rejection. In order to do so, it is sufficient to compute the set of all states of P(A, B) from which some final state can be reached. This can be done by the following ground Datalog program: We define an nfa C(A, B) such that amb C(A,B) (w * η) = concur Q (w, η). The situation is a little different than for D(A, B), in that C(A, B) runs on words annotated by events rather than tuples. We fix a new variable y / ∈ V n that will denote the event of interest, and define the alphabet of C(A, B) to be Σ × 2 {y} . The idea of nfa C(A, B) is to guess a partial candidate τ , until the event marker y comes, and to test whether τ is alive at that event, and to accept in case of success.

p ′ ∈ fin A q ′ ∈ fin B unsafe rej (p, q). p (a,V ) → p ′ ∈ rul A q a → q ′ ∈ rul B unsafe rej (p, q) :-unsafe rej (p ′ , q ′ ).
p 0 p 1 p 2 p 3 ok (a, ∅) (b, ∅) (a, ∅) (b, ∅) (b, ∅) (a, ∅) (b, ∅) (a, {y}) (b,
stat C(A,B) =stat A ×stat B ⊎ {ok} init C(A,B) =init A ×init B fin C(A,B) ={ok} (p, q) (a,V ) → (p ′ , q ′ ) ∈ rul P(A,B) (p, q) (a,∅) → (p ′ , q ′ ) ∈ rul C(A,B) (p, q) (a,V )
→ (p 1 , q 1 )∈rul P(A,B) unsafe sel (p 1 , q 1 ) unsafe rej (p 1 , q 1 ) (p, q) (a,{y})

→ ok ∈ rul C(A,B)
Both rules guess a set of variables V and check that the current position is the denotation of all variables in V , by running automaton A with V in the input letter. The second rule inputs the event marker, and goes into the ok-state, if automaton P(A, B) could move to states that are unsafe for both selection and rejection, so that the current partial candidate is alive. Note that, using Lemmas 16 and 19, C(A, B) can be computed in polynomial time. For illustration, consider Figure 5 which shows the automaton C(A, B) obtained from the automaton A in Figure 3 and the trivial universal automaton B.

Given a word w = a 1 • . . . •a m and a position 1 ≤ η ≤ m we write w|η for the word (a

1 , ∅)•(a η-1 , ∅)•(a η , {y}). Proposition 20. concur Q (A,B) (w, η) = amb C(A,B) (w|η), for all w ∈ L(B) and η ∈ dom(w).
Proof. Let w ∈ L(B) and η ∈ dom(w). Suppose that τ 1 and τ 2 are different partial tuples that are alive at η. Let r 1 and r 2 be the runs of A on the prefixes of w * τ 1 resp. w * τ 2 until η. Since τ 1 and τ 2 are different, there exists a position i such that the prefixes of length i < η of w * τ 1 and w * τ 2 have different types. Since A is canonical, this implies that both runs assign states of different types to position i, so that r 1 (i) = r 2 (i).

Let a 1 • . . . •a η be the prefix of w until position η. By construction of C(A, B), both runs r i restricted to {1, . . . , η-1} are also runs of C(A, B) on word v = (a 1 • . . . •a η-1 ) ⊗ ∅. These runs can be extended to successful runs of C(A, B) on w|η = v•(a η , {y}) by mapping position η to ok, since both tuples τ i are alive at event η (and thus neither safe for selection nor rejection). Both runs are different, since runs r 1 and r 2 differ at some position i < η. Hence concur Q (A,B) (w, η) ≤ amb C(A,B) (w|η).

For the converse, consider two different runs r 1 and r 2 of C(A, B) on w|η. We now build two partial tuples τ 1 and τ 2 and the corresponding runs r ′ 1 and r ′ 2 of A on the prefixes of w * τ 1 and w * τ 2 until η. These are hidden in the rules applied for producing runs r 1 and r 2 by C(A, B). Since the states which are permitted to move to ok are alive, the runs r ′ 1 and r ′ 2 can be extended into an alive state at η. This shows that both tuples τ 1 and τ 2 are alive. They are different, since produced from distinct runs r 1 and r 2 . This shows that amb C(A,B) (w|η) ≤ concur Q A,B (w, η). Theorem 5. Bounded and k-bounded concurrency for queries and schemas defined by canonical dfas can be decided in P-time for any fixed k ≥ 0.

Proof. From Lemmas 16 and 19, C(A, B) can be constructed in P-time from A and B. Before the construction, we need to make A and B productive, which can be done in time O(|A| + |B|). By Proposition 20, it remains to decide the finite (resp. k-bounded) ambiguity of C(A, B). Since k is fixed by assumption, this can be done in P-time according to Theorem 1.

It should be noticed that our results for concurrency problems are weaker than those for delay problems. In particular, we don't know whether the concurrency of a dfa query can be computed in P-time and whether k-bounded concurrency can be decided in P-time for variable k (where k becomes part of the input of the problem). The reason is that we could not come up with a direct automaton construction in the case of concurrency, and that we don't know neither whether k-bounded ambiguity of nfas is in P-time for variable k.

Queries on Unranked Trees by Nested Word Automata

We state our main results on deciding bounded delay and concurrency for queries on unranked trees that are defined by dnwas [START_REF] Alur | Adding nesting structure to words[END_REF][START_REF] Alur | Marrying words and trees[END_REF]. These automata were called deterministic streaming tree automata in [START_REF] Gauwin | Streaming tree automata[END_REF], since they define deterministic streaming algorithms in a natural way. As shown there, the notion of deterministic forest pushdown automata [START_REF] Neumann | Locating matches of tree patterns in forests[END_REF] is equivalent to dnwas too.

Alternatively, we could have decided to work with bottom-up or top-down deterministic tree automata on ranked trees modulo some binary encoding. It is well-known that the same queries can be expressed this way but possibly in a less succinct manner. Intuitively, the notion of determinism of dnwas is advantageous since corresponding naturally to the notion of determinism of streaming algorithms. For this reason it is possible to compile XPath queries in large streamable fragments of XPath to dnwas [START_REF] Gauwin | Streaming Tree Automata and XPath[END_REF][START_REF] Gauwin | Streamable fragments of Forward XPath[END_REF] in polynomial time.

Nested Word Automata

We start by recalling the notion of dnwas. We consider nested words as linearizations of unranked trees. syntax <a><b><c></c></b><d></d></a>. In order to avoid further encodings, we will interpret nwas directly on unranked trees, i.e., as streaming tree automata [START_REF] Gauwin | Streaming tree automata[END_REF].

Definition 21. An nwa is tuple A = (Σ, Γ, stat, init, fin, rul) where Γ is a finite set of stack symbols, stat a finite set of states, init, fin ⊆ stat and rul ⊆ stat 2 × Γ × Σ, that we denote as q 1 α a:γ ---→ q 2 where q 1 , q 2 ∈ stat, α ∈ {op, cl}, γ ∈ Γ, and a ∈ Σ.

Figure 6(a) presents an nwa that accepts all trees with labels in {a, b} that contain some node labeled by a with a child labeled by b. This is the language of the Boolean query defined by the fo formula ∃x.(lab a (x)∧∃y.(ch(x, y)∧lab b (y))) without free variables.

An nwa traverses a tree t in pre-order. It visits every node of t twice, once when entering (open event) and once when exiting (close event) the subtree. An nwa associates a state to each event of t, and a stack symbol to each node of t, as shown in Figure 6(b). This corresponds to operating on the stream of events produced by a Sax parser on the Xml linearization. At every time point, the configuration of an nwa maintains a node, a current state, and a current stack, which is the lists of states annotated to the path to the current node. The height of the stack is thus equal to the depth of the current node.

More formally, a run of an nwa on a tree t is a pair of functions (r e , r n ) with types r e : eve(t) → stat and r n : nod (t) → Γ which map events to states and nodes to stack symbols, such that r e (start) ∈ init and the rule r e (pred ((α, π))) ------→ r e (α, π) belongs to rul for all π ∈ nod (t) with a = lab t (π), and actions α ∈ {op, cl}. The language L(A) is the set of all unranked trees t ∈ T Σ that permit a successful run by A, i.e., r e ((cl, ǫ)) ∈ fin.

An nwa is deterministic or equivalently a dnwa, if it has a single initial state, no two op rules for the same letter use the same event state on the left, and no two cl rules for the same letter use the same stack symbol and the same event state on the left. dnwas can perform one-pass typing for extended DTDs [START_REF] Bray | Extensible markup language (xml) 1.0[END_REF] with restrained competition [START_REF] Martens | Expressiveness and complexity of XML schema[END_REF] as well as for earliest query answering [START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF].

Closure Properties

Language recognizable by nwas enjoy the usual closure properties under Boolean operations, projection, and cylindrification.

We will consider projections Π i : T Σ1×...×Σm → T Σi for all 1 ≤ i ≤ m, such that all Π i (t) relabels all nodes π ∈ nod (t) to the i-th component of its label. We write

t = t 1 * • • • * t m if ∧ m i=1 Π i (t) = t i .
We will also use more general projections operations Π I : T Σ1×...×Σm → T Σi 1 ×...×Σi n that preserve a subset of components

I = {i 1 , . . . , i n } where 1 ≤ i 1 < . . . < i n ≤ m by Π I (t 1 * . . . * t m ) = t i1 * . . . * t in . Projections can be lifted to languages of trees L ⊆ T Σ1×...×Σm by Π I (L) = {Π I (t) | t ∈ L}.
We also need cylindrification operations on tree languages, which may add, copy, and exchange components of tuple trees, but not delete them. We formalize unsorted cylindrification operations that apply to trees L ⊆ T Σ n , where all components have the same signature Σ. For functions θ : {1, . . . , m} → {1, . . . , m} with {1, . . . , n} ⊆ θ({1, . . . , m}) we define:

c θ L = {t θ(1) * . . . * t θ(m) ∈ T Σ m | t 1 * . . . * t n ∈ L}
Note that all newly added components have signature Σ. Sorted cylindrification operations, that add components of particular types, can be obtained from unsorted cylindrification and intersection.

Proposition 22. Languages of unranked trees recognizable by nwas are closed under Boolean operations, projection and cylindrification. The corresponding operations on nwas all preserve determinism except for projection and can be performed in P-time except for complementation non-deterministic nwas. Furthermore every nwa can be made deterministic (in time

O(2 |A| 2 )).
The analogous results are well-known for bottom-up deterministic tree automata on ranked trees. Proposition 22 can be established for dnwas in analogy, or else by compiling nwas to standard tree automata that operate on curried binary encodings of unranked trees (see Appendix B).

It should be noticed that the cylindrification operations c θ here are a little richer than the usual ones c i as in [START_REF] Hubert Comon | Tree automata techniques and applications[END_REF] that insert a single new component at position i. In addition, operators c θ can copy components, which can be tested by intersection with deterministic nwas that recognize the set {t * t | t ∈ T Σ }. They can also permute components. While operation c θ can be implemented in P-time for every fixed θ by computing intersections with a fixed number of tree automata (but not for flexible θ).

Note also cylindrification cannot delete components in contrast to projection since the latter may spoil determinism in contrast to the former.

Querying Unranked Trees by dNWAs

Total n-ary queries Q A on unranked trees in T Σ can be defined by nwas A over Σ × B n that recognize the canonical language of Q. Partial queries Q (A,B) are defined by adding automaton B over Σ that recognizes the domain of the query.

The closure properties of nwas in combination with determinization as stated in Proposition 22 imply that all mso definable n-ary queries on unranked trees are definable by dnwas. Nevertheless, we are able to prove the following theorem:

Theorem 6 (Main). Bounded delay is decidable in P-time for n-ary queries defined by deterministic nested word automata (dnwas) where n may be variable. Bounded concurrency is decidable in P-time for fixed n. For fixed k and n, kbounded delay and concurrency are decidable in P-time.

Unfortunately, our P-time algorithms for dfa-queries on words cannot be lifted to dnwa-queries trees in any straightforward manner. The problem is that the notion of safe states of dfas must be generalized to safe configuration of dnwas where a configuration depends on the current stack in addition. Nevertheless it was shown in [START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF] how to extend some of the automata constructions to dnwa queries. These constructions, however, produce deterministic nwas of exponential size rather than non-deterministic nwas of polynomial size.

In order to solve these problems, we present another proof by reduction to bounded resp. k-bounded valuedness of recognizable relations between unranked trees. We first show that bounded and k-bounded valuedness of nwa-recognized relations between unranked trees can be decided in P-time (Section 7) and then that delay and aliveness of dnwa-queries can be defined by nwas of polynomial size (Section 8).

Recognizable Relations between Unranked Trees

We study recognizable relations between trees in the ranked [START_REF] Hubert Comon | Tree automata techniques and applications[END_REF] and unranked case [START_REF] Benedikt | Logical definability and query languages over ranked and unranked trees[END_REF]. A recognizable relation is a set of tuples of trees such that the set of overlays of these tuples is recognizable by a tree automaton. Similarly to transducers, a notion of valuedness can be associated with binary recognizable relations. We will use valuedness of recognizable tree relations to capture the delay and concurrency of queries.

We first define recognizable relations over unranked trees and provide a key example of such relations. We then present a procedure for deciding the bounded valuedness of binary recognizable relations in polynomial time. The proof is by reduction to bounded valuedness of tree transducers [START_REF] Seidl | Single-valuedness of tree transducers is decidable in polynomial time[END_REF]. We then recall a standard method to define recognizable relations in fo logic from a set of basic recognizable relations, while relying on closure properties of tree automata. Finally, we prove that k-bounded valuedness of binary recognizable relations is decidable in P-time, by reduction to emptiness of tree automata.

An alternative way of proving the P-time decidability of bounded valuedness of recognizable relations could be to use visibly pushdown transducers (vpts) [START_REF] Raskin | Visibly pushdown transducers[END_REF] instead of bottom-up tree transducers. Indeed, vpts directly operate on unranked trees. Functionality (i.e. 1-bounded valuedness) of vpts was proven decidable in P-time recently [START_REF] Filiot | Properties of visibly pushdown transducers[END_REF], but it is still open whether k-bounded valuedness is decidable in P-time (it is known to be in NP-time [START_REF] Filiot | Properties of visibly pushdown transducers[END_REF]). Neither exists there any decidability result for bounded valuedness of vpts.

In this paper, we use nwas as underlying class of tree automata. We could have chosen another class A of unranked tree automata, provided that a) it can be translated in P-time to nwas, and b) A is closed under intersection, complementation, cylindrification and projection modulo P-time transformations, that preserve determinism except for projection. In particular, this is the case for two classes: top-down ntas operating on the fcns encoding of trees, and bottom-up ntas over the curry encoding of trees (see Appendix B for more details). Note however, that hedge automata with dfas for horizontal languages [START_REF] Hubert Comon | Tree automata techniques and applications[END_REF] fail to satisfy these requirements, since deterministic hedge automata cannot be complemented in P-time.

Recognizable Relations

The overlay of k unranked trees t i ∈ T Σ i is the unranked tree t 1 ⊛ . . . ⊛ t k in T Σ 1 ×...×Σ k obtained by superposing these k trees top-down and left-to-right; the symbol represents missing children where the structures of the trees differ. This is illustrated in Figure 7 and formally defined by:

a(t 1 , . . . , t k ) ⊛ b(t ′ 1 , . . . , t ′ l ) = (a, b)(t 1 ⊛ t ′ 1 , . . . , t l ⊛ t ′ l , t l+1 ⊛ , . . . , t k ⊛ ) if l ≤ k (a, b)(t 1 ⊛ t ′ 1 , . . . , t k ⊛ t ′ k , ⊛ t k+1 , . . . , ⊛ t l ) otherwise
Overlays of ranked trees can be obtained this way too [START_REF] Hubert Comon | Tree automata techniques and applications[END_REF], except that overlayed symbols need to inherit the maximal arity. A k-ary relation R between unranked trees is recognizable iff the language of its overlays ovl(R) = {t 1 ⊛ . . . ⊛ t k | (t 1 , . . . , t k ) ∈ R} is recognizable by an nwa. We say that R is recognized by the nwa A if ovl(R) = L(A).

Example: Tree Equality until Some Event

For illustration, we consider the relation eq η (t, u) between unranked trees that expresses the equality of their sequentializations until some event. This holds if t and u have the same structure and labels until event η. The idea now is to represent an event η by some unranked tree, so that equality until some event can be represented by a ternary relation between trees.

More precisely, we represent an event η of t by the unranked tree ren η (t) with signature {0, op, cl}, whose domain coincides with that of t. If the event η = (α, π) is an opening event, then its node π is renamed to op, and in analogy if it is a closing event. All other nodes are renamed to 0. See Figure 8 for a graphical illustration. More formally, let ren (α,π) (t) ∈ T {0,op,cl} be obtained by renaming the label of π to α and the labels of all other nodes of t to 0. We then define the ternary relation Eq ⊆ T Σ × T Σ × T {0,op,cl} such that for all events η ∈ eve(t) and trees t ∈ T Σ : (t, u, ren η (t)) ∈ Eq ⇔ df eq η (t, u)

8: (t, u, ren η (t)) ∈ Eq but (t, u, ren η ′ (t)) / ∈ Eq
Proof. We define a dnwa A on Σ ×Σ ×{0, op, cl} such that L(A) = ovl(Eq).

We use two states stat A = {before, after}, where init A = {before} and fin A = {after}. We use a single dummy stack symbol Γ = { }. The rules are given by the following inference schema:

α ∈ {op, cl} a ∈ Σ b ∈ Σ before α (a,a ,0):
-------→ before before op (a,a,cl):

--------→ before before α (a,a,α):

-------→ after after α (a,b,0):

------→ after after cl (a,b,op):

-------→ after after α ( ,a, ):

-------→ after Note that the rule before op (a,a,cl):

--------→ before is used to check the equality below a node π if prefix equality has to be checked until (cl, π). The nwa A has size O(|Σ 2 |) and can be computed in this time.

Other examples of recognizable relations [START_REF] Benedikt | Logical definability and query languages over ranked and unranked trees[END_REF] are the tree extension relations ≤ ↓ , ≤ → ⊆ T Σ ×T Σ , such that t ≤ ↓ t ′ if t ′ is obtained by repeatedly adding children to leaves of t, and t ≤ → t ′ if t ′ is obtained by repeatedly adding next-siblings to right most children of t.

Bounded Valuedness

Like bottom-up tree transducers on ranked trees, bounded valuedness of recognizable relations over unranked trees is decidable in P-time.

Theorem 7. For every nwa A recognizing a binary relation R between unranked trees, val(R) < ∞ can be decided in P-time in |A|.

Note that A may be non-deterministic. The deterministic case is easier since then the valuedness of R is equal to the ambiguity of the projection of A to the input signature of R. So the problem is that the non-determinism introduced by projection must be properly separated from any non-determinism of A.

Proof. We prove Theorem 7 by a reduction to Theorem 3, i.e. the P-time decision procedure for bounded valuedness of bottom-up (ranked) tree transducers.

Our first reduction is to the analogous problem for the ranked case. Here we use the top-down encoding (fcns) and show that it preserves the valuedness of relations (Proposition 24). Moreover, we can compute in P-time an nta A ′ recognizing the fcns encoding R ′ of R (see Proposition 39).

The second reduction transforms binary relations on ranked tree R to relabeling relation Relab R with the same valuedness. A relabeling relation R ⊆ Proof. The nta A ′ is obtained by adding one more state to A, so that stat(A ′ ) = stat(A) ∪ {q } and fin(A) = fin(A ′ ). Automaton A ′ runs A top-down, until occurs, and then checks for equal domains:

R =            a , f f a a a     ,     a , f a f a a            Relab R =            a , f f a a a     ,     a , f a f a a     ,     a , f f a a a     ,     a , f a f a a     , . . .       
( , ) → q ∈ rul A ′ ( , )(q , q ) → q ∈ rul A ′ (a, b) → q ∈ rul A (a, b)(q , q ) → q ∈ rul A ′ (a, b)(q ) → q ∈ rul A ′ Valuedness preservation is checked in Lemma 40 of Appendix C.
For relabelings over binary trees, bounded valuedness can be tested efficiently.

Proposition 26. The finite valuedness of a binary relabeling recognizable relation R over binary trees can be decided in P-time in |A|, when given an nta A recognizing R.

Proof. Let R ⊆ T bin Σ1 × T bin Σ2 be a relabeling relation for binary signatures, and A an nta for trees in T bin Σ1×Σ2 that recognizes R, i.e. L(A) = ovl(R). We transform A into a bottom-up tree transducer T defining the relation R. The rules of T are inferred as follows where x 1 , x 2 are variables:

(f, g)(q 1 , q 2 ) → q ∈ rul A f (q 1 (x 1 ), q 2 (x 2 )) → q(g(x 1 , x 2 )) ∈ rul T (a, b) → q ∈ rul A a → q(b) ∈ rul T
This transducer T has the same valuedness as R. Theorem 3 shows that it can be decided in polynomial time whether T is finite-valued, i.e. whether R is bounded.

The above construction of bottom-up transducers cannot be lifted to recognizable relations beyond relabelings. This is why we introduced Relab R . Even though testing bounded valuedness of tree transducers is known to be in P-time [START_REF] Seidl | Single-valuedness of tree transducers is decidable in polynomial time[END_REF], the complexity of known polynomial time algorithms is much higher than for testing bounded ambiguity of tree automata [START_REF] Sakarovitch | Decidability of bounded valuedness for transducers[END_REF].

Note that if we add the condition that A is deterministic, then a similar construction could have been done using automata instead of transducers. If A ′ is the automaton on Σ 2 obtained from A by projecting the Σ 1 components, then amb(A ′ ) = val (R), and ambiguity (and k-ambiguity) of A ′ can be obtained in P-time [START_REF] Seidl | On the finite degree of ambiguity of finite tree automata[END_REF][START_REF] Seidl | Deciding equivalence of finite tree automata[END_REF]. However, we will use relations defined by existential firstorder formulas over relation symbols, whose corresponding automata are nondeterministic.

Sorted FO Logic

Just as logics on words give alternative means of specifying regular languages, fo logic on unranked trees gives a means of specifying recognizable relations [START_REF] Benedikt | Logical definability and query languages over ranked and unranked trees[END_REF]. Since we have to deal with relations of trees over various signatures we will use a sorted fo logic, so that signatures can be mapped to sorts.

A sorted relational signature is a relational signature ∆ = Ω⊎ℜ, that consists of a set of monadic symbols ω ∈ Ω called sorts and a set of relation symbols r ∈ ℜ, each of which has a sort sort(r) ∈ Ω ar(r) .

We fix an infinite set V of variables. A sorted fo formula φ over ∆ has the following abstract syntax, where r ∈ ℜ is a relation symbol of arity n, X 1 , . . . , X n , X ∈ V and ω ∈ Ω:

φ ::= r(X 1 , . . . , X n ) | φ ∧ φ ′ | ¬φ | ∃X:ω. φ
Every sorted fo formula can be understood as a unsorted fo formula, obtained by mapping sort bounded quantifiers ∃x:ω.φ to unsorted quantifiers ∃x.(ω(x) ∧ φ); here sorts ω ∈ Ω are used as monadic predicate symbols.

A sorted relational structure s over ∆ = Ω ⊎ ℜ is a relational structure such that: dom(s) = ∪ ω∈Ω ω s and for every relation symbol r ∈ ℜ of arity m:

sort(r) = (ω 1 , . . . , ω m ) ⇒ r s ⊆ ω s 1 × . . . × ω s m
Every sorted fo formula φ over ∆ with at most m free sorted variables defines an m-ary relation for every sorted relational structure s over ∆:

R φ(X1:ω1,...,Xm:ωm

) (s) = Q φ(X1,...,Xm) (s) ∩ ω s 1 × . . . × ω s m
Note that the sorted formula φ in Q φ(X1,...,Xm) is considered as an unsorted fo formula in order to reuse the definition of queries in this new context.

Sorted FO Logic of Recognizable Relations

In what follows let Ω be a fixed collection of unranked alphabets. Note that only the simpler case with a single signature was treated in [START_REF] Benedikt | Logical definability and query languages over ranked and unranked trees[END_REF]. For every sorted relation signature ∆ = Ω ⊎ ℜ, we will write fo ∃ [ℜ] for the set of sorted ∆-formulas in prenex normal form where quantifiers are existential. Definition 27. A sorted structure of tree relations s over ℜ is a sorted relational structure over Ω ⊎ ℜ in which all alphabets Σ ∈ Ω are interpreted as the set of unranked Σ-trees Σ s = T Σ . We call a sorted structure of tree relations s recognizable if all tree relations r s with r ∈ ℜ are recognizable.

A sorted structure of recognizable tree relations over ℜ can be defined by a collection of nwas {A r } r∈ℜ defining a recognizable relation between unranked trees for every relation symbol. While overloading notion, we will write s = {A r } r∈ℜ for the sorted structure of tree relations defined by these automata.

Every sorted fo formula φ with at most m free sorted variables defines an m-ary relation:

R φ(X1:Σ1,...,Xm:Σm) (s)

⊆ T Σ1 × • • • × T Σm
The closure properties of nwas under Boolean operations, cylindrification, and projection ensure that all such relations are recognizable. Furthermore, under some assumptions, an nwa recognizing the relation defined by an fo ∃ [ℜ] formula can be computed efficiently from the nwas {A r } r∈ℜ .

Proposition 28. Let φ be a fixed formula in fo ∃ [ℜ] with at most m free sorted variables X 1 :Σ 1 , . . . , X m :Σ m where X i ∈ V and Σ i ∈ Ω. Then there exists a polynomial p such that for all sorted structures of recognizable tree relations s = {A r } r∈ℜ defined by nwas such that A r is deterministic if r occurs in the scope of a negation in φ, one can compute in time p( r∈ℜ |A r |) an nwa that recognizes the relation R φ(X1:Σ1,...,Xm:Σm) (s). The computed nwa is deterministic, if all automata are deterministic and φ is free of existential quantifiers.

Proof. The proposition relies of the closure properties of nwas. The proof, which is by induction on the structure of formulas in fo ∃ [ℜ], is mostly standard and presented in detail in Appendix C. Note that all automata in the construction remain deterministic, except for those capturing outermost existential quantification.

In the remainder of this section, we prove that k-bounded valuedness of nwarecognized relations is decidable in P-time too. There, we will use the above proposition for the first time. Further applications will follow in Section 8, in order to construct nwas of polynomial size, that recognize relations capturing delay and concurrency of dnwa defined queries.

k-Bounded Valuedness

In this section we study the problem of deciding whether a binary recognizable relation has k-bounded valuedness. We first for all fixed k that k-bounded valuedness is decidable in P-time. Subsequently we consider the problem for variable k, and prove that it becomes exptime-hard.

Note that we cannot obtain a P-time decision for k-bounded valuedness by using transducers, in contrast to Proposition 26, since known algorithms for deciding k-boundedness of transducers are in coNP-time (Theorem 2.2 of [START_REF] Seidl | Equivalence of finite-valued tree transducers is decidable[END_REF]).

We can neither reduce the problem to deciding k-ambiguity of tree automaton. We will need to measure the valuedness of relations that capture delay and concurrency, but in general, amb(A) and val (R) may be uncomparable even for tree automata A recognizing relation R. Proof. We consider the tree relation SameTree = {(t, t) | t ∈ T Σ2 } which is recognizable by an nwa of size O(|Σ 2 | 2 ). We fix a binary relation symbol r and a relation symbol SameTree. For every relation R we define a structures s R such that r sR = R and SameTree sR is the relations with the same name. We define a formula val >k with k + 2 free variables in the logic of recognizable relations in fo ∃ [r, SameTree], such that R val >k (X:TΣ 1 ,X1:TΣ 2 ,...,X k+1 :TΣ 2 ) (s R ) = ∅ if and only if val (R) > k:

val >k = df 1≤i≤k+1 r(X, X i ) ∧ 1≤i<j≤k+1 ¬SameTree(X i , X j )
An nwa recognizing relation R val >k (X:Σ1,X1:Σ2,...,X k+1 :Σ2) (s R ) = ∅ can be computed in polynomial time from the nwa A, where the polynomial depends on the fixed parameters |Σ 1 |, |Σ 2 | and k. This follows from Proposition 28 since relation symbol r does not occur below negation in formula val >k . Emptiness of the language of this automaton can be tested in linear time. Hence, there exists a polynomial p (depending on the fixed parameters k, Σ 1 , and Σ 2 ), such that we can check val (R) > k in polynomial time O(p(|A|)) from an nwa A recognizing R.

Theorem 8 provides a P-time decision procedure for k-bounded valuedness, under the assumption that k is fixed. The proof relies on an nwa of size O(|A| k+1 ) and a complexity bound of O(p(|A| k+1 )) for some polynomial p. Without bounding k, however, this algorithm can only be shown to be in exptime.

Theorem 9. The problem that inputs k ∈ N 0 and an nwa A recognizing a binary relation R between unranked trees, and outputs the truth value of val(R) ≤ k is exptime-complete.

Proof. As argued above, the algorithm proving Theorem 8 runs in exptime if not bounding k. For the hardness part, we will reduce emptiness of intersection of deterministic nwas to this problem [START_REF] Alur | Adding nesting structure to words[END_REF][START_REF] Seidl | Haskell overloading is DEXPTIME-complete[END_REF]. Let Int(S) be the problem that inputs S, a finite sequence of dnwas, and outputs "yes" if and only if there is at least one tree recognized by each automaton of the sequence. For each nwa A ∈ S, consider the binary relation R A that associates trees t with accepting runs of A on t: R A = {(t, r) | r is a run of A on t}. From A ∈ S, we can build in polynomial time an nwa recognizing R A . So, from S -w.l.o.g. we suppose that the set of states are disjoint -we construct in polynomial time an nwa A S for the binary relation ∨ A∈S R A . As the automata are deterministic, A S will be (|S|-1)-bounded iff there isn't any tree recognized by each automaton of the sequence. The conclusion follows, because emptiness of intersection of dnwas is exptime-hard [START_REF] Alur | Adding nesting structure to words[END_REF][START_REF] Seidl | Haskell overloading is DEXPTIME-complete[END_REF].

Using the above constructions and Theorem 5.5 of [START_REF] Seidl | Equivalence of finite-valued tree transducers is decidable[END_REF], we can build an algorithm for computing the exact value of val (R), if it exists. The overall complexity is a fixed number of exponentials in |A|.

Deciding Bounded Delay and Concurrency

We prove our main Theorem 6 on deciding bounded delay and concurrency for queries defined by dnwas by reduction to bounded valuedness of recognizable relations.

Basic Recognizable Relations

We start by defining various relations between trees by dnwas, that we will use later on for defining the delay and concurrency of dnwa-defined queries by recognizable relations between trees.

In this section, we fix the alphabets Ω = {Σ, {0, op, cl}} ∪ n {2 Vn } and consider the sorted relational signature ∆ = Ω ⊎ ℜ with relation symbols ℜ = {Can, Bef&Can, Bef&NotCan, Bef • , S, Eq Σ , SameTuples}∪ n {Eq 2 Vn , Type1 n }. Given an n-ary query Q, we define in the sequel the sorted structure of tree relations s Q over ℜ by providing interpretations of the symbols in ℜ. We denote the interpretations by indexing them with Q. For instance, S is always mapped to the schema associated with the query, so that S Q = dom(Q).

The relation Eq ⊆ T Σ × T Σ × T {0,op,cl} has been introduced in Section 7.2. We use it on alphabets Σ and 2 Vn , hence defining Eq Σ and Eq 2 Vn respectively.

Type1 n

Since states of canonical nwas need no more to be typed (the type of a tree recognized in a state may vary with the current stack content), we consider unary relations Type1 n ⊆ T 2 Vn that are equal to the set of trees of T 2 Vn of type 1 Vn . Lemma 29. A dnwa recognizing Type1 n can be computed in time O(3 n ).

Proof. Here we just have to collect variables in states at opening tags, and read only variables that have not been seen so far.

stat=2 Vn init={∅} fin={V n } Γ={ } V, V ′ ⊆ V n V ∩ V ′ = ∅ V op V ′ : ----→ V ∪ V ′ ∈ rul V ′ ⊆ V ⊆ V n V cl V ′ : ----→ V ∈ rul
This dnwa can be computed in time O(3 n ): For opening rules, choosing V and V ′ consists in determining for each variable

x ∈ V n whether x ∈ V -V ′ , x ∈ V ′ -V or x / ∈ V ∪ V ′ .
Similarly, for closing rules, we have to choose whether

x ∈ V -V ′ , x ∈ V ′ , or x / ∈ V ∪ V ′ .

Can

The next kind of tree relations express canonical languages of queries. Given a tree t ∈ T Σ and a complete tuple τ ∈ dom(t) n , we define a tree prune τ (t) ∈ T 2 Vn as follows. Let t ′ be the prefix of t with domain dom latest(τ ) (t). We set prune τ (t) = Π 2 (t ′ * τ ).

For every n-ary query Q, we define a recognizable relation Can Q ⊆ T Σ ×T 2 Vn , which relates trees t ∈ T Σ with tuples τ ∈ Q(t): Proof. The dnwa A recognizes the relation {(t, Π 2 (t * τ )) | τ ∈ Q(t)}. Hence only pruning of the second component is missing. This is obtained by doing the product of A with a modified version of the dnwa recognizing Type1 n (Lemma 29), where opening actions are forbidden after reaching state V n .

Can Q = {(t, prune τ (t)) | τ ∈ Q(t)}

Bef&Can

The relation Bef = {(t, prune τ (t), ren η (t)) | τ ∈ dom η (t) n } is the subset of T Σ × T 2 Vn × T {0,op,cl} that captures all n-tuples of nodes of t (on its second component) that contain only nodes opened before an event η provided by the third component. Bef is recognizable by a dta of size O(3 n ), so we cannot use this relation for P-time algorithms without fixing n. The problem can be circumvented by using the following relation Bef&Can Q which can be recognized while using the states of the canonical automaton for L(Q) for checking types:

Bef&Can Q = {(t, ren τ (t), ren η (t)) ∈ T Σ × T 2 Vn × T {0,op,cl} | τ ∈ Q(t) ∧ τ ∈ dom η (t) n }
where ren τ (u) ∈ T 2 Vn is the projection of u * τ to 2 Vn , i.e., nod (ren τ (u)) = nod (u) and lab ren τ (u) (π) = V if lab u (π) = (a, V ) for some a ∈ Σ, and all π ∈ nod (u).

Lemma 31. We can compute a dnwa A B&C recognizing Bef&Can Q(A,B) in time O(|A|).

Proof. We define stat A B&C = stat A × B, in order to control by a Boolean, whether the third component has been seen before. We define initial states by init A B&C = init A × {0}, final states by fin A B&C = fin A × {1}, and stack symbols by Γ A B&C = Γ A . Before reaching event η, we run A on t * τ :

q 0 α (a,V ):γ ------→ q 1 ∈ rul A α ′ = α (q 0 , 0) α (a,V,α ′ ):γ --------→ (q 1 , 0) ∈ rul A B&C
When reaching η, we change the Boolean value:

q 0 α (a,V ):γ ------→ q 1 ∈ rul A (q 0 , 0) α (a,V,α):γ -------→ (q 1 , 1) ∈ rul A B&C
After η, we only allow empty annotations at opening (i.e., no variables):

q 0 α (a,V ):γ ------→ q 1 ∈ rul A α ′ = α α = op ⇒ V = ∅ (q 0 , 1) α (a,V,α ′ ):γ --------→ (q 1 , 1) ∈ rul A B&C

Bef&NotCan

We also need a negated version of Bef&Can. The relation

Bef&NotCan Q = {(t, ren τ (t), ren η (u)) ∈ T Σ × T 2 Vn × T {0,op,cl} | τ / ∈ Q(t) ∧ τ ∈ dom η (t) n ∧ dom η (t) = dom η (u)}
is the subset of T Σ × T 2 Vn × T {0,op,cl} that captures all tuples τ (on its second component) that contain only nodes opened before an event η provided by the third component, such that τ / ∈ Q(t).

Lemma 32. We can compute a dnwa

A B&N C recognizing Bef&NotCan Q(A,B) in time O(|A|).
Proof. The dnwa A B&N C is similar to A B&C , but final states are inverted, and the structure of the η-component may differ from the first two ones after η. This second feature requires to be able to stop and resume the run of A on the first two components. We use the stack to store the current state when a run of A is stopped, and add a state (and stack symbol) to go through subtrees belonging only to the η-component. The automaton A B&N C also has to check that all descendants and right-siblings of -labelled nodes must be labelled by on the corresponding component. The full construction is technical but not difficult, and omitted for clarity. Every step can be performed in O(|A|), as only empty annotations are allowed after reading η.

SameTuples

The relation SameTuples checks whether two tuples are equal until a given event, the first one being selected by the query: We define a variant of Bef for partial tuples, called Bef • . Here, we do not try to avoid the blow-up for two reasons. First, Bef • will be used with Type1 n , and a blow-up is necessary to recognize Type1 n . Second, separating the relations permits to clarify the definition of the formula capturing concurrency.

SameTuples Q = {(t, ren τ (t), u τ ′ , ren η (t)) ∈ T Σ × T 2 Vn × T 2 Vn × T {0,op,cl} | τ ∈ Q(t)
The relation Bef

• = {(ren τ (t), ren η (t)) | ∃t ∈ T Σ . τ ∈ (dom η (t) ∪ {•}) n } is a subset of T 2 Vn × T {0,
op,cl} that relates annotations of trees with tuples τ and events η, such that latest(τ ) ≤ η.

Lemma 34. A dnwa recognizing Bef

• can be computed in time O(3 n ).
Proof. The following dnwa recognizes the relation Bef • . In the states, we collect (at opening) variables corresponding to the components of τ that have been encountered. We also add a Boolean, that indicates whether the event η has been read. Note that on the second component, we can read values different from 0 when we are not at η. For instance if η = (op, π), we will read "op" on the second component when we go through (cl, π).

stat=2 Vn × B init={(∅, 0)} fin=2 Vn × {1} Γ={ }
Rules are defined by the following inference schemas. At opening, we check canonicity if η has not been reached; otherwise we forbid variables in the first component. When η is reached, we still allow to read variables, and change the Boolean.

α ∈ {0, cl} V, V ′ ⊆ V n V ∩ V ′ = ∅ (V, 0) op (V ′ ,α): -------→ (V ∪ V ′ , 0) ∈ rul (V, 0) op (V ′ ,op): -------→ (V ∪ V ′ , 1) ∈ rul (V, 1)
op (∅,0):

------→ (V, 1) ∈ rul At closing, we do not check anything. We just change the Boolean when η is reached.

δ ∈ B α ∈ {0, op} V ′ ⊆ V ⊆ V n (V, 0) cl (V ′ ,cl): -------→ (V, 1) ∈ rul (V, δ) cl (V ′ ,α): -------→ (V, δ) ∈ rul
The complexity comes from the same argument as Lemma 29.

Bounded Delay

Our objective is to define the formulas delay Q and concur Q in the logic fo ∃ [Eq, Can, S, Bef , Bef&Can, Bef&NotCan, SameTuples] preferably without using Can and Bef (to avoid a 3 n blowup). We start with the definition of the relation

Sel Q = {(t, prune τ (t), ren η (t)) | (τ, η) ∈ sel Q (t)} by an fo formula Sel with three free variables, such that Sel Q = R Sel(Xt:Σ,Xτ :2 Vn ,Xη:{0,op,cl}) (s Q ): Sel = df S(X t ) ∧ Bef (X t , X τ , X η ) ∧ ∀X ′ t :Σ. (S(X ′ t ) ∧ Eq Σ (X t , X ′ t , X η )) ⇒ Can(X ′ t , X τ ) Note that entailment of Can(X ′ t , X τ
) is correct only since we prune trees using Bef : if (t ′ , t, η) belongs to relation R Eq(Xt:Σ,X ′ t :Σ,Xη:{0,op,cl}) (s Q ) then t and t ′ may have different domains beyond η. Given dnwas A and B defining Q = Q (A,B) we can thus define a dnwa recognizing Sel Q (X t , X τ , X η ). Unfortunately, we cannot construct this dnwa in P-time yet, since formula Sel does not belong to the existential fragments of fo and uses relations Can and Bef . Nevertheless, we obtain an algorithm for deciding judgments (τ, η) ∈ sel Q (t).

We define the relation Delay Q = {(t, ren τ (t), ren η (t)) | η ∈ delay Q (t, τ )} by the following formula of fo ∃ [Eq, Bef&Can, Bef&NotCan, S, SameTuples], that expresses that η is an event increasing the delay if the nodes of τ ∈ Q(t) are before η in t, and there is a tree t ′ that equals t until η but with τ / ∈ Q(t ′ ). The formula has 3 free variables such that Delay Q = R Delay(Xt:Σ,Xτ :2 Vn ,Xη:{0,op,cl}) (s Q ).

Delay = df ∃X ′ t :Σ. ∃X ′ τ :2 Vn . S(X t ) ∧ Bef&Can(X t , X τ , X η ) ∧ S(X ′ t ) ∧ Bef&NotCan(X ′ t , X ′ τ , X η ) ∧ Eq Σ (X t , X ′ t , X η ) ∧ SameTuples(X t , X τ , X ′ τ , X η )
All base relations can be defined by dnwas computed in P-time when leaving n variable (since we do not need the relations Can and Bef here, and by Lemmas 23, 31, 32 and 33). Given deterministic automata A and B, we can thus define a possibly non-deterministic automaton recognizing Delay Q (A,B) (X t , X τ , X η ) in P-time from A and B, by Proposition 28. Let 2Delay

Q = {(t ⊛ u τ , u η ) | (t, u τ , u η ) ∈ Delay Q }.
Both relations are recognized by the same automaton. This relation exactly captures the delay:

val (2Delay Q ) = max τ ∈Q(t) delay Q (t, τ )
Thus we can decide bounded delay and k-bounded delay of Q for a fixed k in P-time by Theorems 7 and 8.

Bounded Concurrency

For concurrency, we proceed in a similar manner, except that we have to work with partial (incomplete) tuples. Completion raises new difficulties, since after the event η, we allow non-empty annotations on the 2 Vn component, which requires a blowup wrt. n.

Q = {(t, ren τ (t), ren η (t)) | (τ, η) ∈ alive Q (t)}.
Proof. We define Alive Q by a formula of fo ∃ [S, Can, Eq Σ , Eq 2 Vn , Type1 n , Bef • ], such that Alive Q = R Alive(Xt:TΣ,Xτ :T 2 Vn ,Xη:T {0,op,cl} ) (s Q ). Here we use the relation Eq with two different alphabets: Σ and 2 Vn . The latter permits to express completions of tuples.

Alive

(X t ,X τ ,X η ) = df ∃X ′ t ∈ T Σ . ∃X ′′ t ∈ T Σ . ′ τ ∈ T 2 Vn . ∃X ′′ τ ∈ T 2 Vn . S(X ′ t ) ∧ S(X ′′ t ) ∧ Can Q (X ′ t , X ′ τ ) ∧ Eq Σ (X t , X ′ t , X η ) ∧ Eq 2 Vn (X τ , X ′ τ , X η ) ∧ Bef • (X τ , X η ) ∧ ¬Can Q (X ′′ t ,X ′′ τ ) ∧ Eq Σ (X t ,X ′′ t ,X η ) ∧ Eq 2 Vn (X τ ,X ′′ τ ,X η ) ∧ Type1 n (X ′′ τ )
This formula expresses that τ is alive at η of t ∈ T Σ if there exists continuations t ′ , t ′′ ∈ T Σ of t beyond η and two completions τ ′ , τ ′′ of τ beyond η such that τ ′ ∈ Q(t ′ ) but τ ′′ / ∈ Q(t ′′ ). Bef • checks whether latest(τ ) ≤ η. Type1 n verifies that X ′′ τ is canonical, as this is not done by ¬Can Q (X ′′ t ,X ′′ τ ). All relations used in the formula are recognizable by dnwas that can be computed in P-time by Lemmas 23, 30, 34 and 29, so that an nwa for Alive Q is obtained in P-time from Proposition 28 (since A is deterministic). Indeed, this result remains true if B is non-deterministic, since relation symbol S does not occur below negation.

Note that we cannot integrate the canonicity control for X ′′ t into the negated relation ¬Can(X ′′ t ,X ′′ τ ). The deeper problem is that automata A for canonical languages of queries Q (A,B) do not have a notion of safe states in the case of trees, since safety depends also on the current stack content.

Let 2Alive Q be the binary version of Alive Q , i.e., 2Alive

Q = {(t ⊛ u η , u τ ) | (t, u η , u τ ) ∈ Alive Q }, then: val (2Alive Q ) = max t∈dom(Q),η∈eve(t) concur Q (t, η)
Since we can define relation 2Alive Q by automata that we can compute in Ptime for fixed n from A and B by Proposition 28 we can decide bounded and k-bounded concurrency of Q for fixed n and k in P-time by Theorems 7 and 8.

Conclusion.

In this paper we proved that bounded delay and concurrency are decidable in P-time for queries in words defined by dfas and for queries in unranked trees defined by dnwas. We obtained analogous results for k-bounded delay and k-bounded concurrency for fixed k.

We presented a direct P-time algorithm that computes the delay of queries in words, and P-time reductions of various boundedness problems for queries in words to ambiguity of nfas, which are know to be decidable in P-time. In the case of trees, we presented P-time reductions for the boundedness problems of queries to bounded valuedness of recognizable relations between trees. We then show how to decide k-boundedness of recognizable relations for fixed k by reduction to emptiness of tree automata, and that k-boundedness for flexible k becomes exptime-hard. We proved that bounded valuedness of recognizable relations is decidable in P-time by reduction to bounded valuedness of tree transducers [START_REF] Seidl | Single-valuedness of tree transducers is decidable in polynomial time[END_REF].

In follow-up work, we have proposed streaming models based on the notion of bounded concurrency and obtained conp-hardness results for boundedness problems for fragments of XPath, and distinguished a fragment of Forward XPath with bounded concurrency [START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF]. An open question is how to obtain a direct algorithm for deciding bounded valuedness of recognizable relations without applying results on tree transducers. This could help to lower the polynomials in our complexity results. In future work, we would like to study lower bounds based on concurrency in sufficient generality. Every nta A over Σ ⊥ defines a language of unranked trees modulo the fcns encoding L(A) = {t ∈ T Σ | fcns(t) ∈ L bin (A)}. Deterministic Dtds can be recognized by top-down deterministic ntas this way (see [START_REF] Champavère | Efficient inclusion checking for deterministic tree automata and XML schemas[END_REF] for precise translations).

The bottom-up encoding is based on currying. Let Σ @ = Σ ⊎ {@} be the ranked alphabet in which all symbols from Σ are constants, and @ is the only binary symbol. Function curry : T Σ → T bin Σ @ maps unranked tree over Σ to binary trees over the ranked signature Σ @ : curry(a(t 1 , . . . , t k )) = a if k = 0 @(curry(a(t 1 , . . . , t k-1 )), curry(t k )) otherwise A stepwise tree automaton [START_REF] Carme | Querying unranked trees with stepwise tree automata[END_REF] is a nta over Σ @ . Every stepwise tree automaton B defines a language of unranked trees modulo currying L(B) = {t ∈ T Σ | curry(t) ∈ L bin (B)}. The notions of bottom-up determinism of ntas on binary trees induce a notion of bottom-up and left-to-right determinism for stepwise tree automata on unranked trees (see [START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF] for discussion).

Appendix B.2. Relation to NWAs

Furthermore, deterministic stepwise tree automata [START_REF] Carme | Querying unranked trees with stepwise tree automata[END_REF] can be converted in dnwas in P-time.

Lemma 37. Every nta over Σ ⊥ can be transformed to a nwa in P-time, such that the language of unranked trees is preserved modulo the fcns-encoding. This transformation preserves top-down determinism, in that it maps d ↓ ntas to dnwas.

Proof. Let A be a nta recognizing binary fcns encodings in T Σ ⊥ . We define an nwa A ′ over Σ such that L(A) = L(A ′ ). This is illustrated by Figure B.11, with runs of A on fcns(t) and A ′ on t.

stat A ′ = stat A init A ′ = fin A fin A ′ = stat A a(q 1 , q 2 ) → q ∈ rul A q op a:q2 ----→ q 1 ∈ rul A ′ ⊥ → q 1 ∈ rul A a ∈ Σ q 2 ∈ stat A q 1 cl a:q2 ----→ q 2 ∈ rul A ′
This transformation maps d ↓ ntas to dnwas. Its correctness can be proved by showing the following invariant: If h = (t 1 , . . . , t k ) is a hedge over Σ, then there is a run r of A on fcns'(h) iff there is a run r ′ of A ′ on h, and if such runs exist, then, if π ′ is the root of t 1 and π the corresponding node in fcns'(h) we have:

Lemma 38.

Stepwise tree automata can be transformed in P-time to nwas with the same language of unranked trees modulo currying. This transformation preserves bottom-up determinism, i.e. it maps dtas to dnwas.

Proof. Modulo currying, stepwise tree automata can be seen as a weaker form of nwas: a stepwise tree automaton evaluates hedges from left to right. The difference with nwas is that when evaluating a new tree of the hedge, the state resulting from the evaluation of the beginning of the hedge is unknown. The translation of a nta A to an nwa A ′ is detailed and proved below, and illustrated by Figure B.12. The key idea here is to translate an @-rule by a closing rule, that uses the stack to know how the hedge of preceding siblings of the current node was evaluated, and the current state to know what is the state for the subtree rooted at the current node. Labels are only used at opening.

stat A ′ = stat A ⊎ {i, f} init A ′ = {i} fin A ′ = {f} @(q 0 , q 1 ) → q 2 ∈ rul A q 1 cl a:q0 ----→ q 2 ∈ rul A ′ a → q 1 ∈ rul A q 0 ∈ stat A ∪ {i} q 0 op a:q0 ----→ q 1 ∈ rul A ′ q ∈ fin A a ∈ Σ q cl a:i

---→ f

Correctness relies on the following property, that can be proved by induction on the structure of t ∈ T Σ @ : a run r of A on t exists iff there is a run r ′ of A ′ on curry -1 (t), and r(ǫ) = r ′ ((cl, k)) if the root of curry -1 (t) has k children, and r ′ ((op, ǫ)) = r(π ǫ ) where π ǫ is the first leaf of t in pre-order. The next proposition states that all three classes of automata have the same expressiveness. They capture monadic second-order definable languages of unranked trees (see e.g. [START_REF] Carme | Querying unranked trees with stepwise tree automata[END_REF] for stepwise tree automata).

Proposition 39 (Same expressiveness). The three classes of tree automata over unranked trees that we consider (ntas wrt. fcns and curry encodings, and nwas) permit determinization and recognize the same languages of unranked trees modulo P-time automata translations (not always preserving determinism).

Proof. For standard tree automata, determinization is standard. For nwas, it is well-known too; it can be obtained from determinization of stepwise tree automata and the translations discussed here. We have already shown how to convert ntas modulo both encoding to nwas (Lemmas 37 and 38). It remains to provide inverse encodings.

nwas to ntas wrt. fcns encoding. Let A be an nwa over the alphabet Σ. We define the nta A ′ over Σ ⊥ such that L(A ′ ) = L(A):

stat A ′ = stat A × stat A fin A ′ = init A × fin A q 0
op a:γ ----→ q 1 ∈ rul A q 2 cl a:γ ----→ q 3 ∈ rul A q 4 ∈ stat A a((q 1 , q 2 ), (q 3 , q 4 )) → (q 0 , q 4 ) ∈ rul A ′ q ∈ stat A ⊥ → (q, q) ∈ rul A ′ Figure B.13 illustrates this translation. The following property is easy to prove by induction on the structure of t, and gives the main idea of the construction: There is a run r ′ of A ′ on t iff there is a run r of A on the hedge fcns -1 (t), and if such runs exist then r ′ (ǫ) = (q 0 , q 1 ) iff there is a run of A on fcns -1 (t) starting in q 0 and ending in q 1 . nwas to ntas over curry encoding. We exhibit a translation from an nwa A to a nta recognizing the language of corresponding curry encodings of trees. This time the translation is more intricate, as nwas allow to send the current state from one node to its right sibling, but ntas over curry encoding do not. This is why we have to guess this state, and then to check whether this guess corresponds to the state reached when closing the previous sibling. The construction is shown above and illustrated by Figure B.14.

stat A ′ = Σ × stat A × stat A q 0
op a:γ ----→ q 1 ∈ rul A a → (a, q 1 , q 1 ) ∈ rul A ′ q 0 op a:γ ----→ q 1 ∈ rul A q 2 cl a:γ ----→ q 3 ∈ rul A q 0 ∈ init A q 3 ∈ fin A (a, q 1 , q 2 ) ∈ fin A ′ q 0 op b:γ ----→ q 1 ∈ rul A q 2 cl b:γ ----→ q 3 ∈ rul A q 4 , q 5 ∈ stat A a ∈ Σ @((a, q 4 , q 0 ), (b, q 1 , q 2 )) → (a, q 4 , q 9 ) ∈ rul A ′

The following invariant can be proved inductively on the structure of t ∈ T Σ @ : There is a run r ′ of A ′ on t such that r ′ (ǫ) = (a, q 0 , q 1 ) iff the root of curry -1 (t) is labeled by a, there is a run r of A on curry -1 (t) such that r((op, ǫ)) = q 0 and r((cl, k)) = q 1 where k is the last child of the root.

• either lab vi (π) = and lab vj (π) = : then π belongs to nod (t i ) and to nod (t j ) and lab ti (π) = lab tj (π).

• either lab vi (π) = and lab vj (π) = : then π belongs to nod (t i ) and π does not belong to nod (t j ).

• either lab vj (π) = and lab vi (π) = : similar to the precedent case.

So, there exists t ∈ T Σ 1 such that there exists at least k distinct t i with (t, t i ) ∈ R.

Proposition 28.

Let φ be a fixed formula in fo ∃ [ℜ] with at most m free sorted variables X 1 :Σ 1 , . . . , X m :Σ m where X i ∈ V and Σ i ∈ Ω. Then there exists a polynomial p such that for all structures of recognizable relations s = {A r } r∈ℜ defined by tree automata such that A r is deterministic if r occurs in the scope of a negation in φ, one can compute in time p( r∈ℜ |A r |) an automaton that recognizes the relation R φ(X1:Σ1,...,Xm:Σm) (s). The computed automaton is deterministic, if all automata are deterministic and φ is free of existential quantifiers.

Proof. The proof follows from two claims, that relate operations on tree relations to operations on tree languages closure properties of tree automata.

) ovl(Q 1 ∧ Q 2 ) = ovl(Q 1 ) ∩ ovl(Q 2 )
Proof of Claim 41. The proof is straightforward from the definitions. The next claim relates connectives of sorted fo formulas to operations on tree relations. Claim 42. For all alphabets Σ = (Σ 1 , . . . , Σ m ) and Σ m+1 , variables X = (X 1 , . . . , X m ) and X m+1 that are pairwise distinct, structures s of tree relations, functions θ : {1, . . . , m} → {1, . . . , m} with {1, . . . , n} ⊆ θ({1, . . . , m}), sorted formulas φ, φ 1 , φ 2 in fo[ℜ], and relations symbols r ∈ ℜ: ovl(R ∃Xm+1:Σm+1.φ( X: Σ) (s)) = Π {1,...,m} (ovl(R φ( X: Σ,Xm+1:Σm+1) (s))) ovl(R r( X)(X θ(1) :Σ θ(1) ,...,X θ(m) :Σ θ(m) ) (s)) = ovl(T Σ θ(1) × . . . × T Σ θ(m) ) ∩ c θ ovl(r s ) ovl(R φ1∧φ2( X: Σ) (s)) = ovl(R φ1( X: Σ) (s)) ∩ ovl(R φ2( X: Σ) (s)) ovl(R ¬φ( X: Σ) (s)) = ovl(T Σ1 × . . . × T Σm )ovl(R φ( X: Σ) (s))

Proof of Claim 42. The proof is straightforward from the definitions and the previous claim. For illustration, we elaborate the case of negation, where the sorting information is needed. Let L Σ = ovl(T Σ1 × . . . × T Σm ). ovl(R ¬φ( X: Σ) (s)) = L Σ ∩ ovl(Q ¬φ( X: Σ) (s)) = L Σ ∩ (L Σovl(Q φ( X: Σ) (s))) (previous claim) = L Σovl(R φ( X: Σ) (s))

Figure 1 :

 1 Figure 1: Top-down binary encoding

Figure 3 :

 3 Figure 3: Automaton A for the query selecting a-nodes followed by b•b. There are two reachable unsafe states of type {x 1 } = V 1 , p 1 and p 2 . The restriction of A to these two states is acyclic, so the selection delay of Q A is bounded. It is bounded by 2, since the longest path in this part of the automaton has 2 nodes.

Lemma 12 .

 12 If A and B are productive, then all safe states of Q (A,B) that are reachable in P(A, B) are productive and have type V n .

Figure 4 :Theorem 4 .

 44 Figure 4: nfa D(A, B) for the dfa A in Figure 3 with trivial universal B. The ambiguity of D(A, B) is 2 (on word (a, {x 1 })•(b, ∅) for instance), such as the delay of Q (A,B) .

  This program can be constructed in time O(|A| • |B|) from A and B. By Proposition 36, the lfp(P ) can be computed in time O(|A| • |B|).

Figure 5 :

 5 Figure 5: nfa C(A, B) for query dfa A in Figure 3 and trivial universal B. Even though non-deterministic, the ambiguity of C(A, B) is 1, equally to the concurrency of Q (A,B) .

Figure 6 :

 6 Figure 6: An nwa accepting all trees with some a-node with b-child, i.e., for the fo formula ∃x.(laba(x) ∧ ∃y.(ch(x, y) ∧ lab b (y))).

Figure 7 :

 7 Figure 7: Example for overlays

Lemma 23 .

 23 For every signature Σ we can compute a dnwa in time O(|Σ| 2 ), that recognizes the relation Eq ⊆ T Σ × T Σ × T {0,op,cl} . Tree ren η (t) with η = (1, cl).

  ren η ′ (t) with η ′ = (2, op).

Figure

  Figure 8: (t, u, ren η (t)) ∈ Eq but (t, u, ren η ′ (t)) / ∈ Eq

Figure 9 :

 9 Figure 9: A recognizable relation R and the relabeling Relab R with the same valuedness.

Theorem 8 .

 8 Let Σ 1 and Σ 2 be two alphabets and k ∈ N 0 fixed. There exists a polynomial p such that for every relation R ⊆ T Σ1 × T Σ2 recognized by a possibly non-deterministic nwa A, val(R) ≤ k can be decided in time p(|A|).

Lemma 30 .

 30 Let A and B be dnwas that define an n-ary query Q = Q (A,B) . Then we can compute a dnwa from A in time O(|A| • 3 n ) that recognizes Can Q .

Proposition 35 .

 35 If arity n ∈ N is fixed, then for every n-ary query Q = Q (A,B) defined by dnwas A and B, we can compute in P-time a possibly nondeterministic nwa that recognizes the relation Alive

  Figure B.10: Binary encodings

  r ′ e ((op, π ′ )) = r(π•1) and r ′ n (π ′ ) = r(π•2). A run of a nta A on t ∈ T Σ ⊥ .A run of the corresponding nwa A ′ on fcns -1 (t).

Figure B. 11 :

 11 Figure B.11: Example of runs for the translation of ntas modulo fcns encoding to nwas.

Figure B. 12 :

 12 Figure B.12: Example runs for the translation of ntas for curry encoding to nwas.

  A run of the nwa A on t ∈ T Σ . A run of the corresponding nta A on fcns(t).

Figure B. 13 :

 13 Figure B.13: Example runs for the translation of nwas to ntas wrt. fcns encoding.

  A run of the nwa A on t ∈ T Σ . q1, q1) (b, q2, q2) (a, q1, q3) (c, q4, q4) (a, q1, q5) (a, q1, q9) (d, q6, q6) (e, q7, q7) (d, q6, q8)(b) A run of the corresponding nta A ′ on curry(t).

Figure B. 14 :

 14 Figure B.14: Example runs for the translation of nwas to ntas modulo curry encoding.

Claim 41 .

 41 For all Q ⊆ T Σ1 ×. . .×T Σm , V m = {X 1 , . . . , X m and θ : {1, . . . , m} → {1, . . . , m} with {1, . . . , n} ⊆ θ({1, . . . , m}):ovl(∃X i .Q) = Π {1,...,i-1,i+1,...,m} (ovl(Q)) ovl(c θ Q) = c θ ovl(Q) ovl(¬Q) = ovl(T Σ1 × . . . × T Σm )ovl(Q

  p 1 and p 2 . The restriction of A to these two states is acyclic, so the selection delay of Q A is bounded. It is bounded by 2, since the longest path in this part of the automaton has 2 nodes.

Building P(A, B) requires time in O((|Σ|+n)•|A|•|B|), if we suppose for instance that variables in V are stored in a vector of n bits. Lemma 11. Let A and B be productive dfas that define a query, and r a run of P(A, B) on w * τ and η ∈ eve(w). Then state r(η) is safe for selection by Q (A,B) if and only if (τ, η)

  {y})

	unsafe sel unsafe rej	unsafe sel unsafe rej	unsafe sel unsafe rej	unsafe rej

  and Eq 2 Vn (ren τ (t), u τ ′ , ren η (t)) and nodes of u τ

′ opened after η are labeled by ∅} Lemma 33. A dnwa A SameTuples recognizing SameTuples Q(A,B) can be computed in time O(|A|).

Proof. The dnwa A SameTuples recognizing SameTuples can be obtained by running A on t * τ and t * τ ′ simultaneously until η, and then allowing the τ ′component to have a different structure, labeled only with ∅. Hence the proof uses the same technique as proof of Lemma 32.

8.1.6. Bef •

INRIA, Lille

University of Lille 1

Mostrare project, INRIA & LIFL (CNRS UMR8022)

Note that the notion of concurrency used in the introduction did not take the empty tuple into account. This just differs the concurrency from 1.

Acknowledgments.

We thank the reviewers for their helpful comments on the revision of this article. This work was partially supported by the Enumeration project ANR-07-blanc and the project CODEX of ANR-08-Defis.

T Σ 1 × . . . × T Σ n is a relation between trees of the same structure, i.e. whenever (t 1 , . . . , t n ) ∈ R then nod (t 1 ) = . . . = nod (t n ). In other words, the overlays in ovl(R) do not contain any place holder . Proposition 25 shows that val (R) = val (Relab R ), and provides a P-time procedure to compute an nta A ′ recognizing Relab R , from an nta A recognizing R.

Finally, the third reduction reduces the bounded valuedness problem of recognizable relabeling relations to bounded valuedness of bottom-up tree transducers (see Proposition 26).

Let ren be the morphism on binary trees that renames constants ( , . . . , ) to and preserves the trees otherwise. This morphism is linear and one-toone, so it preserves regularity in both directions: L is recognizable iff ren(L) is recognizable. Overlays of unranked and ranked trees are related in the following way:

The following proposition shows that valuedness is preserved by the fcns encoding. Let fcns(R) = {(fcns(t

An example is given in Figure 9. While the relation R there is finite, the corresponding relabeling Relab R is infinite, since there may be infinitely many witnesses for every pair of R.

Proposition 25. Relab R and R have the same valuedness. Moreover, an nta A ′ recognizing Relab R can be computed from an nta A recognizing R in time O(|A|).

Appendix A. Ground Datalog

We recall some folklore definitions and results about ground Datalog, frequently used in this paper. For more details, we invite the reader to refer to the following papers [START_REF] Ceri | What You Always Wanted to Know About Datalog (And Never Dared to Ask)[END_REF][START_REF] Dantsin | Complexity and expressive power of logic programming[END_REF][START_REF] Gottlob | Datalog LITE: a Deductive Query Language with Linear Time Model Checking[END_REF].

Let Λ be a ranked signature containing constants c ∈ Λ and predicates p ∈ Λ, where all predicates have an arity ar(p) ∈ N 0 . We call a term p(c 1 , . . . , c ar(p) ) a literal, and denote the set of literals over Λ by lit(Λ). A clause is a pair in lit(Λ) × lit(Λ) k (with k ∈ N 0 ) that we write L :-L 1 , . . . , L k . as usual. A ground Datalog program P is a finite set of clauses over Λ. Its size |P | is the total number of symbols appearing in all its clauses.

The least fixed point lfp(P ) of P is the least set of literals over Λ that satisfies that for all clauses L :-L 1 , . . . , L k . of P , if L 1 , . . . , L k ∈ lfp(P ) then L ∈ lfp(P ). As no negation is allowed, every ground Datalog program P has a unique least fixed point, and this one is finite. For ground Datalog, this least fixed point can be efficiently computed.

Proposition 36. For every signature Λ and every ground Datalog program P over Λ, the least fixed point of P can be computed in time O(|P |).

Proof. A program P can be seen as an hypergraph: vertices are literals, and edges are tuples (L, L 1 , . . . , L k ) such that L :-L 1 , . . . , L k . is a clause of P . Then the least fixed point of P is exactly the set of accessible literals in this hypergraph. This can be computed in linear time, modulo the ability of testing whether L = L ′ in time O(1). This is trivial if all literals are constants, but we have to prove it for arbitrary signatures.

We can do this by assigning a number to each literal in P . This is done in O(|P |) by parsing P and using a prefix tree that stores the assigned numbers of all encountered literals. For instance the prefix tree #(p 2 (c 2 (c 1 (1), c 2 (2)))) (where # is just an extra symbol) indicates that p 2 (c 2 , c 1 ) is assigned to 1, and p 2 (c 2 , c 2 ) to 2.

Appendix B. NWAs versus Standard Tree Automata

In this section, we relate nwas on unranked trees to standard tree automata on ranked trees with respect to expressiveness. We also show that the notion of determinism of dnwas generalizes over both bottom-up and top-deterministism of standard tree automata in a succinct manner. This implies that Theorem 6 does equally apply to queries defined by top-down deterministic tree automata on top-down encodings of unranked trees (fcns), or by bottom-up deterministic tree automata on bottom-up encodings (curry).

Appendix B.1. Binary Encodings

The top-down encoding is defined by a function fcns : T Σ → T bin Σ ⊥ and is illustrated in Figure 10(b). Its definition is based on an encoding of hedges, fcns' : Proof. If ex i (t, t ′ ) holds for (t, t ′ ) ∈ T Σ i × T Σ i , then we write clean i (t ′ ) = t, which is well-defined as t is unique for a given t ′ . It is easy to check that:

First, let us prove that the valuedness of Relab R is at least the valuedness of R. Let t in T Σ 1 such that there exists at least k distinct t i with (t, t i ) ∈ R.

For a tree u and a set of nodes D such that nod (t) ⊆ D, we define the completion of u w.r.t. D as the tree u D defined by nod

Now, let us prove that the valuedness of Relab R is at most the valuedness of R. Let u in T Σ 1 such that there exists at least k distinct v i with Relab R (u, v i ). Let t = clean 1 (u), t i = clean 2 (v i ): we have (t, t i ) ∈ R. It remains to prove that the t i are all distinct.

Let 1 ≤ i < j ≤ n: as v i = v j there exists a position π such that lab vi (π) = lab vj (π): Finally, we illustrate the induction proving Proposition 28 for formula φ = ¬φ ′ . Since φ ∈ fo ∃ [ℜ], formula φ ′ cannot contain existential quantifiers. Furthermore, all automata A r for relations symbols occurring in φ must be deterministic by assumption. By induction hypothesis, there exists a polynomial p ′ such that for all structures s = {A r } r∈ℜ defined automata automata A r , one can compute in time p( r∈ℜ |A r |) a deterministic automaton A ′ recognizing the language ovl(R φ ′ ( X: Σ) (s)). Recall that ovl(R φ( X: Σ)(s)) is equal to ovl(T Σ1 × . . . × T Σm )ovl(R φ ′ ( X: Σ) (s)) as shown by the previous claim. We obtain an automaton A recognizing this language by complementing A ′ and intersecting it with an automaton for ovl(T Σ1 × . . . × T Σm ). This can be done in time The only construction, where non-determinism is needed are projections. This is why we require existential quantifiers to appear only in prenex position. Note that the proposition can be extended to general fo formulas, but not in P-time.