Groz Benoît

Mostrare

Sebastian Maneth

Staworko Sławek

Deterministic Regular Expressions in Linear Time

Keywords: F.2.2, I.1.1 DTD, XML Schema, Deterministic Regular Expression, Glushkov Automaton, Linear Time

Deterministic regular expressions are widely used in XML processing. For instance, all regular expressions in DTDs and XML Schemas are required to be deterministic. In this paper we show that determinism of a regular expression e can be tested in linear time. The best known algorithms, based on the Glushkov automaton, require O(σ|e|) time, where σ is the number of distinct symbols in e. We further show that matching a word w against an expression e can be achieved in combined linear time O(|e| + |w|), for a wide range of deterministic regular expressions: (i) star-free (for multiple input words), (ii) bounded-occurrence, i.e., expressions in which each symbol appears a bounded number of times, and (iii) bounded plus-depth, i.e., expressions in which the nesting depth of alternating plus (union) and concatenation symbols is bounded. Our algorithms use a new structural decomposition of the parse tree of e. For matching arbitrary deterministic regular expressions we present an O(|e| + |w| log log |e|) time algorithm.

INTRODUCTION

Deterministic regular expressions are widely used in XML processing. For instance, all regular expressions in DTDs and in XML Schemas are required to be deterministic. The idea stems from the earlier SGML standard where righthand sides of context-free productions ("content models") are deterministic regular expressions. Such expressions can be parsed more efficiently than unrestricted ones.

Within XML databases and XML processing, the two main tasks performed over regular expressions are (1) testing determinism and (2) matching (= parsing) against (child sequences of) the given input document.

Testing Determinism. The original terminology used in SGML was to restrict content models to be "unambiguous"; it means that at any position in the regular expression (positions are labeled by symbols, such as a or b, but not by operators such as * ) and for each symbol there may be at most one position that follows. For instance, the expression ab * b is ambiguous because the a-position is followed by two b-positions. Intuitively, the parser upon reading ab has to choose against which b to parse. There exist many translations from regular expressions to finite automata, see e.g. [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]. The particular translation due to Glushkov [START_REF] Glushkov | The abstract theory of automata[END_REF] (see also [START_REF] Berry | From regular expressions to deterministic automata[END_REF]) associates to each position a state of the automaton. As Brüggemann-Klein shows [START_REF] Brüggemann-Klein | Regular expressions into finite automata[END_REF], a regular expression is unambiguous if and only if its Glushkov automaton is deterministic. We therefore use the term "deterministic regular expression." Brüggemann-Klein's result allows to test determinism of an expression e as follows: (i) build the Glushkov automaton A of e and (ii) test determinism of A. The worst-case size of A is O(σ|e|), where σ is the number of distinct symbols in e, and A can be built and checked for determinism in this time bound. Thus, this test has quadratic time complexity in the size of e. It is a general misconception in the literature that testing determinism of regular expressions can be performed in linear time (cf. e.g., the abstract of [START_REF] Brüggemann-Klein | Regular expressions into finite automata[END_REF]). The known algorithms build the Glushkov automaton in quadratic worst-case time. Note that large alphabets appear in practice, and that the quadratic behavior of building the Glushkov automaton is experienced even for very simple expressions such as E = (a1 + a2 + • • • + am) * .

For the expression E, determinism can easily be checked in linear time (by checking distinctness of the ai). The "mixed content" of XML, for instance, is similar to E and some XML validators such as Xerces [START_REF]Xerces-C++ ver. 3.1.1[END_REF] use specialized linear time procedures for this case. For more complicated expressions, however, it has remained open whether linear time determinism testing is possible. Here we close the problem affirmatively and show that all regular expressions can be tested for determinism in time O(|e|). Our idea is a new decomposition of e's parse tree. For each distinct symbol a of e we build its "skeleton"; roughly speaking, it is a tree consisting of all positions labeled a, plus their iterated LCAs (lowest common ancestors) in e's parse tree; skeleton trees can be obtained in linear time [START_REF] Bojanczyk | XPath evaluation in linear time[END_REF] using preprocessing and constant time LCA [START_REF] Bender | Lowest common ancestors in trees and directed acyclic graphs[END_REF] queries. By adding more nodes and pointers into the skeleton trees, we are able to test determinism in linear time.

Matching. Consider now matching a deterministic regular expression e against an input word w. What makes it difficult to match e against w? We identify several "easy" cases: (i) Star-free: in this case, |w| ≤ |e|, and we can match easily during one traversal over the parse tree of e. (ii) Bounded number of distinct symbols in e: we simply build the Glushkov automaton. (iii) Bounded number of occurrences of each symbol in e (k-occurrence): Here we use our first technical lemma. It says that testing if two positions follow each other in e (this means the Glushkov automaton has a transition between the positions) can be realized in constant time. This is achieved by preprocessing e's parse tree for LCA [START_REF] Bender | Lowest common ancestors in trees and directed acyclic graphs[END_REF] and by using LCA queries to realize a structural relationship of follow positions known from [START_REF] Chang | From regular expressions to DFA's using compressed NFA's[END_REF][START_REF] Ponty | A new quadratic algorithm to convert a regular expression into an automaton[END_REF]. Hence, we do not build the Glushkov automaton. Since at most k positions need to be checked for the follow relationship when matching against a k-occurrence expression, the lemma implies linear time O(|e|+k|w|). Note that for real world DTDs it has been reported that a large percentage of regular expressions is k-occurrence for small k [START_REF] Bex | Learning deterministic regular expressions for the inference of schemas from XML data[END_REF][START_REF] Martens | Expressiveness and complexity of XML Schema[END_REF].

One finding is that plus-symbols (union) play an essential role in the combined complexity of matching. For instance, if no plus-symbols in e are nested, then we show that matching can be done in time O(|e| + |w|). The idea is to annotate particular nodes in e's parse tree with candidates of followpositions in e. The determinism requirement of e then allows to amortize the number of annotated nodes that have to be visited in order to go from one symbol in w to the next.

Our amortization argument fails when the depth of alternation of plus and concatenation symbols is not bounded. Such expressions seem the hardest to match, and finding a time O(|e| + |w|) algorithm remains an open problem. Note that the alternation depth is small in practice: Grijzenhout's large collection of real-world DTDs [START_REF] Grijzenhout | Quality of the XML web[END_REF] does not contain a single expression with alternation depth larger than 4. We present an algorithm with time O(|e| + |w| log log |e|) complexity that works for arbitrary deterministic expressions. It is derived from our linear time determinism test which assigns colors (i.e., labels in Σ) to nodes of e's parse tree. At a position p, the next position labeled a is obtained by a lookup at the lowest ancestor of p with color a. The expression e is preprocessed for lowest colored ancestor queries, using [START_REF] Muthukrishnan | Time and space efficient method-lookup for object-oriented programs[END_REF] (based on van Emde Boas trees). Note that for arbitrary (nondeterministic) regular expressions, the best known time complexities are time O(nm/ log n + (n + m) log n) [START_REF] Myers | A four russians algorithm for regular expression pattern matching[END_REF] which was improved recently to O(nm(log log n)/(log n) 3/2 + n + m) [START_REF] Bille | Faster regular expression matching[END_REF], where m = |e| and n = |w|.

Our results are summarized as follows:

(1) Determinism of a regular expression e can be tested in time O(|e|). This improves previous algorithms requiring quadratic time. Besides a direct proof, we present an alternative one which uses a fixed XPath query, and then applies the result of Bojańczyk and Parys [START_REF] Bojanczyk | XPath evaluation in linear time[END_REF].

( (3) Star-free deterministic regular expression can be matched against several input words w1, . . . , wn, in time Recently it was proved that even in the presence of numeric occurrence indicators (as used in XML Schema), determinism of expressions can be tested in time O(σ|e|) [START_REF] Kilpeläinen | Checking determinism of XML schema content models in optimal time[END_REF]. We show that our result extends to this case: even in the presence of numeric occurrence indicators we can decide determinism in time O(|e|). We note that all our matching algorithms are streamable, i.e., they do not need to store w in memory, but read w in one sequential pass, symbol by symbol. We have implemented all our algorithms and made them available at http://gforge.inria.fr/projects/lire/.

O(|e| + |w1| + • • • + |wn|). (4

Related Work

The idea of our algorithm [START_REF] Bex | Learning deterministic regular expressions for the inference of schemas from XML data[END_REF], and also to a lesser extent of our determinism check [START_REF] Bender | Lowest common ancestors in trees and directed acyclic graphs[END_REF], is similar to that of Hagenah and Muscholl [START_REF] Hagenah | Computing epsilon-free NFA from regular expressions in O(n log 2 (n)) time[END_REF] in their algorithm that computes for any regular expression an ε-free NFA in time Ω(|e| log 2 |e|). They decompose the transitions leaving each state into a few sets and group states sharing such sets of outgoing transitions. This decomposition is based on a heavy path decomposition of the parse tree of e. We use another decomposition of this parse tree in order to amortize the evaluation cost.

An orthogonal direction of research involves algorithms for the efficient validation of huge documents against a small DTD. Several works [START_REF] Segoufin | Constant-memory validation of streaming XML documents against DTDs[END_REF][START_REF] Segoufin | Validating streaming XML documents[END_REF] focused on obtaining space efficient algorithms in a streaming framework. This is challenging when document trees are deep. Konrad and Magniez [START_REF] Konrad | Validating XML documents in the streaming model with external memory[END_REF] provide streaming algorithms in sublinear space for the validation against DTDs. They consider a framework where the algorithm has access to a read-only input stream and several auxiliary read/write streams. The algorithm is allowed to perform read or write passes on the streams. At the beginning of each pass on a stream, the algorithm decides in which direction the stream is processed, and also decides if the pass is a write or a read pass. The authors propose an algorithm that validates a tree t against a constant-size DTD in O(log 2 |t|) passes, using space O(log |t|) and 3 auxiliary streams, with O(log |t|) processing time per symbol. Note that the validator checks the sibling sequences of t against the corresponding deterministic regular expression.

In the context of DTD inference, Bex et al. identify two classes of regular expressions which account for most of the regular expressions in real schemas: the single occurrence regular expressions (1-ORE) and the chain regular expressions (CHARE). An expression is an 1-ORE iff no symbol appears more than once in e, therefore 1-ORE are always deterministic. CHARE are a subclass of 1-ORE, and contain the 1-ORE that consist of a sequence of factors of the form (a1 +a2 +• • •+an) where every ai is a symbol, each factor being possibly extended with a star or a question mark. 1-ORE account for 98% of the regular expressions in real schemas, while CHARE account for 90% of them. Bex, Neven, and van den Bussche [START_REF] Bex | DTDs versus XML Schema: A practical study[END_REF] also define simple regular expressions, which generalize CHARE in that symbols ai in factors can appear with a star or question mark, and the number of occurrences of a symbol is not restricted.

The class of expressions for which our algorithm (2b) performs in linear time properly contains deterministic simple regular expressions. Moreover although stars are allowed in simple regular expressions, which makes them unfit for algorithm (3), those stars can occur only above a single symbol, or above a union of strings (with possibly a star or question mark above the strings). Therefore, an easy extension of algorithm (3) handles simple deterministic regular expressions.

REGULAR EXPRESSIONS

Let Σ be a finite set of symbols. Regular expressions over Σ are defined by the following grammar, where represents concatenation, + union, ? choice, and * the Kleene star: e := a(a ∈ Σ) | (e) (e) | (e)+(e) | (e)? | (e) * . The language L(e) of e is defined as usual [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]. Note that L((e)?) = L(e) ∪ {ε}, where ε denotes the empty word. We say that e is nullable if ε ∈ L(e). In expressions, we do not write parentheses around words over Σ and often omit symbols. We require of our regular expressions e that:

(R1) e = (#e )$ and # and $ do not appear in e (R2) ((e ) * ) * does not appear in e (R3) if (e )? appears in e, then ε / ∈ L(e )

An arbitrary regular expression can be changed easily (in linear time) into an equivalent one of the required form. Note that # and $ are tacitly present and required, but, for better readability, are omitted in most examples.

We identify a regular expression with its parse tree (as illustrated in Figure 1), and define the positions Pos(e) of e as the leaves of e whereas Ne denotes the set of all nodes from e. For a node n ∈ Ne we denote by e/n the subexpression of e rooted at n. Every tree t is implemented as a pointer structure, where Lchild t(n) (resp. Rchild t(n)) returns the left (resp. right) child of node n in t and parent t (n) returns the parent of n in t. The pointers return Null if the respective node does not exist. For unary nodes Rchild t(n) returns Null . We denote by labt(n) the label of n in t, and by t the (reflexive) ancestor relationship in t. If m t n then we also say that n is a descendant of m. Thus, each node is ancestor and descendant of itself.

The size of a tree t, denoted |t|, is the number of nodes in t, whereas the depth of t depth(t) is the length of path from the root to the deepest node in t. Our restrictions (R2) and (R3) guarantee that |e| is linear in |Pos(e)|. We denote by e the regular expression obtained from e by marking the i-th position (from left to right) with subscript i. We denote by Σ the set of symbols obtained from Σ by adding subscripts below symbols. In particular, Pos(e) = Pos(e).

Given a position p of e, Follow e(p) is the set of positions that may follow p in e:

Follow e(p) = {q | ∃u, v ∈ Σ * , u • labe(p) • labe(q) • v ∈ L(e)}.
The expression e is deterministic if for all p, q, q ∈ Pos(e) with q, q ∈ Follow e(p): q = q implies that labe(q) = labe(q ). Whenever the regular expression or the tree is clear from context, we drop the subscript and write Follow , lab, and . [a]

Regular expression e0

Structure of Regular Expressions

The First and Last-positions of a regular expression e are

First(e) = {p | ∃u ∈ Σ * , labe(p) • u ∈ L(e)} Last(e) = {p | ∃u ∈ Σ * , u • labe(p) ∈ L(e)}.
We also define, for a node n of e, First(n) and Last(n) as First(e/n) and Last(e/n), respectively. Note that First(n) and Last(n) are non-empty for every node n of e. For instance, for the expression e0 in Figure 1 First(n2) = {p1, p2} and Last(n2) = {p5}. Given two nodes u, v of e, let LCA(u, v) denote the lowest common ancestor of u and v in e. The next lemma was stated before, e.g., in [START_REF] Chang | From regular expressions to DFA's using compressed NFA's[END_REF][START_REF] Ponty | A new quadratic algorithm to convert a regular expression into an automaton[END_REF], but not in terms of LCA. Lemma 2.2. Let p, q ∈ Pos(e) and n = LCA(p, q). Then q ∈ Follow (p) iff (1) lab(n) = , q ∈ First(Rchild (n)), p ∈ Last(Lchild (n)), or

(2) q ∈ First(s) and p ∈ Last(s) where s is the lowest * -labeled ancestor of n.

Lemma 2.2 says that there are only two ways in which positions follow each other: (1) through a concatenation, or (2) through a star. We write q ∈ Follow e (p) if (1) is satisfied, and q ∈ Follow * e (p) if ( 2) is satisfied. For instance, in e0 (Figure 1), we have p4 ∈ Follow e 0 (p3) and p1 ∈ Follow * e 0 (p5). Note, however, that there may exist some positions p and q that satisfy simultaneously (1) and [START_REF] Berry | From regular expressions to deterministic automata[END_REF].

It was also observed earlier, e.g., [START_REF] Chang | From regular expressions to DFA's using compressed NFA's[END_REF][START_REF] Ponty | A new quadratic algorithm to convert a regular expression into an automaton[END_REF][START_REF] Hagenah | Computing epsilon-free NFA from regular expressions in O(n log 2 (n)) time[END_REF], that First and Last-sets (and nullability) can be defined in a syntaxdirected way over the parse tree of e. For instance, if lab(n) = and Lchild (n), Rchild (n) are non-nullable then First(n) = First(Lchild (n)) and Last(n) = Last(Rchild (n)). We define now the Boolean properties SupFirst and SupLast for every node n, where n denotes parent(n):

SupFirst(n) iff lab(n ) = , n = Rchild (n ), and
Lchild (n ) is non-nullable SupLast(n) iff lab(n ) = , n = Lchild (n ), and
Rchild (n ) is non-nullable.
If SupFirst(n) then the First-set changes at n's parent: First(parent(n)) ∩ First(n) = ∅, and otherwise is a superset: First(parent(n)) ⊇ First(n). For instance, in e0 (Figure 1), n4 is a SupFirst-node since First(n3) = {p2} and First(n4) = {p4, p5}. This explains the name "SupFirst": a node with this property is "maximal" with respect the Firstsets of its direct descendants (without the property). The same holds for SupLast and Last. We define for any node n, the pointers pSupFirst(n) and pSupLast(n) as the lowest ancestors x of n such that SupFirst(x) and SupLast(x), respectively. Recall that by (R1), e = (#e )$; this implies that for every node of e , both pSupFirst(n) and pSupLast(n) are defined. These definitions will never be applied to the "help nodes" of e that are not in e (such as the root node of e); note however, that the root n1 in Figure 1 is a SupFirstnode (because of the phantom position # not shown in the figure). We can check membership in First and Last, using pSupFirst and pSupLast.

Lemma 2.3. Let p ∈ Pos(e) and n ∈ Ne.

(1) p ∈ First(n) iff pSupFirst(p) n p, and

(2) p ∈ Last(n) iff pSupLast(p) n p.
It is well-known, see [START_REF] Harel | Fast algorithms for finding nearest common ancestors[END_REF][START_REF] Bender | Lowest common ancestors in trees and directed acyclic graphs[END_REF], that arbitrary LCA queries on a tree t can be answered in constant time, after preprocessing of t in linear time. For positions p and q, define the Boolean checkIfFollow (p, q) as true iff q ∈ Follow (p).

Theorem 2.4. After preprocessing of e in O(|e|) time, checkIfFollow (p, q) can be answered in constant time for every p, q ∈ Pos(e).

Proof. First preprocess e for LCA queries. Next, add to each node n of e the pointers pSupLast(n), pSupFirst(n), and pStar (n). The latter points to the lowest * -labeled ancestor of n. Clearly, this preprocessing can be carried out in time O(|e|). We are ready to compute checkIfFollow (p, q) in constant time: first obtain n = LCA(p, q). By Lemmas 2.2 and 2.3 we return true (1) if lab(n) = , pSupFirst(q) Rchild (n), and pSupLast(p) Lchild (n). These conditions can be checked in constant time (n n can be realized, e.g., by testing if LCA(n, n ) = n). If case (1) fails then we compute n = pStar (n) and check in constant time if pSupFirst(q) n and pSupLast(p) n . We return true if the checks succeed and false otherwise.

The following technical lemmas state relationships between positions and their pSupFirst and pSupLast nodes.

Lemma 2.5. Let p, q ∈ Pos(e) and q ∈ Follow e(p). Then (1) parent(pSupFirst(q)) p and

(2) parent(pSupLast(p)) q.

Proof. To show (1), assume that parent(pSupFirst(q)) is not an ancestor of p. Then n = LCA(p, q) is an ancestor of parent(pSupFirst(q)), hence pSupFirst(q) n. By Lemma 2.3(1) we obtain q ∈ First(n) and therefore, by Lemma 2.2, q does not follow p. Point (2) can be proved similarly.

Lemma 2.6. Let p and q be two positions of e such that q follows p. If pSupLast(p) parent(pSupFirst(q)) then pSupFirst(q) is nullable.

Proof. Let p, q ∈ Pos(e) such that q ∈ Follow (p) and pSupLast(p) parent(pSupFirst(q)), and let x = LCA(p, q). Assume first that q ∈ Follow (p). Then lab(x) = and there are no SupLast nodes between p and pSupLast(p) except pSupLast(p). It means that in particular Rchild (x) is nullable. Hence pSupFirst(q) is nullable if it is the rightchild of x. Otherwise pSupFirst(q) is an ancestor of x. In that case, there are no SupFirst nodes between q and pSupFirst(q), except pSupFirst(q), so that Lchild (x) is nullable. Consequently, x is nullable, and there are no SupFirst nor SupLast nodes between x and pSupFirst(q), except the node pSupFirst(q). Therefore, pSupFirst(q) is nullable. The case q ∈ Follow * (p) is handled similarly: pStar (x) is nullable and satisfies pSupFirst(q) pStar (x)

x. Moreover there are no SupFirst nor SupLast nodes between x and pSupFirst(q), except pSupFirst(q). Thus, pSupFirst(q) is nullable.

TESTING DETERMINISM

To test determinism we need to check for every a ∈ Σ and positions q = q labeled a whether there exists a p such that q and q follow p. The challenge of a linear time algorithm is to deal with the quadratically many candidate pairs (q, q ).

Candidate Pair Reduction

We define the following condition: (P1) for all q = q in Pos(e), pSupFirst(q) = pSupFirst(q ) implies lab(q) = lab(q ).

Clearly, if (P1) is false then e is non-deterministic. To see this, let q = q and n = pSupFirst(q) = pSupFirst(q ). Since the First and Last sets of any node are non-empty, there exists a p in Last(Lchild (parent(n))). Note that parent(n) = LCA(p, q) = LCA(p, q ). By Lemma 2.2, q, q ∈ Follow e(p), and hence by definition of determinism, lab(q) = lab(q ). Testing (P1) in linear time is straightforward: during one traversal of e we group the positions with same pSupFirstpointer; for each group we check that all contained positions have distinct labels. This can easily be achieved in linear time, using an adapted bucket sorting algorithm. Therefore we assume from now on that (P1) is true. According to Lemma 2.5(1) we store information about p in the parent of pSupFirst(p). For each position p labeled a, we

• assign color a to the node parent(pSupFirst(p))

• say that position p is a witness for color a in the node parent(pSupFirst(p)).

Observe that each node may be assigned several colors, but, since (P1) holds, each node has at most one witness per color. In Figure 1, node n3 has colors a and c. The witness for color a (resp. c) in n3 is p4 (resp. p5). Lemma 2.5 states that a position q labeled a that follows p is a witnesses for color a in some ancestor of p. Thus, if two positions labeled a follow p, then each of them is witness for color a in ancestors of p.

We say that a node n ∈ Ne has class a if n has color a, or n is a position labeled a, or n is the lowest common ancestor of two nodes of class a. The a-skeleton ta of e consists of all nodes n of class a plus their pSupLast and pStar nodes (as defined in Section 2). The node labels in ta are taken over from e, and the tree structure is inherited from e: n is the left (resp. right) child of n in ta if (1) n is in the subtree of the left (resp. right) child of n in e, (2) n n , and (3) there is no n in ta with n n n . If a node has no left (resp. right) child defined in this way, then the corresponding pointer is set to Null . Note that a node in ta can be labeled or + and have its left (or right) child point to Null . Figure 1 presents a regular expression and its a-skeleton.

Lemma 3.1. The collection of a-skeleta for all a ∈ Σ can be computed in time O(|e|).

Proof. The size of the a-skeleton is linear in the number of positions labeled a in e. Hence the size of the collection of a-skeleta is linear in |e|. The skeleta can be constructed in linear time by simply applying LCA repeatedly, inserting each position from e in left-to-right order using the linear preprocessing so that the LCA of two nodes of e is obtained in constant time. This construction is detailed in Proposition 4.4 of [START_REF] Bojanczyk | XPath evaluation in linear time[END_REF].

In the a-skeleton ta, we equip each node n with three pointers: Witness(n, a), FirstPos(n, a), Next(n, a). For every node n in ta,

• if n has color a then Witness(n, a) is the witness for color a in n (and is undefined otherwise)

• FirstPos(n, a) is the position p labeled a such that p ∈ First(n) if it exists (and is undefined otherwise); note that property (P1) guarantees that there is at most one such position p

• Next(n, a) is the set of all positions in FollowAfter e (n) labeled a.

The set FollowAfter e (n) is the extension of Follow to internal nodes n of e,

FollowAfter e (n) = {q n | ∃p ∈ Last(n), q ∈ Follow e(p)}.
Constructing the data structures FirstPos and Witness is straightforward: Witness is built simultaneously with the a-skeleton; FirstPos can for instance be computed in a single bottom-up traversal of each a-skeleton, using pointers pSupFirst from e and ancestor queries in e. Let n be the root node of the a-skeleton. Then BuildNext(a, n, ∅) in Algorithm 1 builds the data structure Next(n , a) for all nodes n of the a-skeleton.

(¬SupLast(n) or parent ta (n) = parent e (n)) 6 then Y ← Y ∪ {FirstPos(n , a)} 7 Next(n, a) ← {p ∈ Y | n p} 8 if lab(n) = * 9 then Y ← Y ∪ {FirstPos(n, a)} 10 if |Y | > 2 11 then return false 12 if Lchild ta (n) = Null 13 then return true 14 else B ← BuildNext(a, Lchild ta (n), Y ) 15 if Rchild ta (n) = Null 16 then return B 17 else return B ∧ BuildNext(a, Rchild ta (n), Y ) end procedure
the current node n has an ancestor u labeled * with no SupLast-node on their path, then Y contains FirstPos(u, a); if n is in the left subtree of an ancestor u labeled with no SupLast-node on their path, and n has a right sibling n in ta, then Y contains FirstPos(n , a). These conditions imply that the set defined in Line 7 holds all a-labeled positions in FollowAfter e (n). Clearly, e is non-deterministic if |Y | > 2 in Line 10.

We define another condition: (P2) for every a ∈ Σ and n ∈ Nt a , Next(n, a) contains at most one element.

Clearly, (P2) can be tested in linear time (for instance by incorporating it into Algorithm 1). If (P2) is false, then e is non-deterministic. Thus, from now on we assume that both (P2) and (P1) are true. We identify Next(n, a) with q if Next(n, a) = {q}, and let it be undefined otherwise.

Lemma 3.3. Let p, q ∈ Pos(e) with labe(q) = a. If q ∈ Follow e(p) then the lowest ancestor n of p having color a exists and satisfies q = Witness(n, a) or q = FirstPos(n, a) or q ∈ Next(n, a).

Proof. By Lemma 2.2, Lemma 2.5 (1), and Lemma 3.2: q = Witness(n, a) if Rchild (n) e q, q = FirstPos(n, a) if Lchild (n) e q, and q = Next(n, a) if n e q.

From Lemma 3.3 and the definition of (P1) and (P2) we obtain the following result.

Lemma 3.4. The expression e is non-deterministic iff (P1) or (P2) is false, or there exist a ∈ Σ, n ∈ Nt a of color a, and q, q ∈ {FirstPos(n, a), Witness(n, a), Next(n, a)} such that q = q and Follow -1 e (q) ∩ Follow -1 e (q ) = ∅.

Determinism Testing Algorithm

To check determinism using Lemma 3.4 we need to check for a ∈ Σ and n ∈ Nt a of color a, and for every pair of distinct positions q and q in {FirstPos(n, a), Witness(n, a), Next(n, a)} whether or not Follow -1 e (q) ∩ Follow -1 e (q ) = ∅. Three combinations can occur for a position p: The third combination, however, reduces to the other two and therefore needs not be considered: let F and N denote the nodes Next(n, a) and FirstPos(n, a), and let nF and nN denote the parent of their SupFirst-node. We can prove that either nF nN n, in which case F = FirstPos(nN , a) (and N = Witness(nN , a)), or nN nF n, in which case N is one of FirstPos(nF , a) or Next(nN , a) (and F = Witness(nF , a)).

To understand the first combination, consider the expression e = (c(b?a?))a, and let n be the parent of the c node in e. Thus, n is of color a, with the left a in e as witness. Clearly e is non-deterministic: take p as the c position, then both Witness(n, a) and Next(n, a) follow p. The same holds for the expressions e = (c(a?b?))a and e = (c(b?a) * )a. However, expression e = (c(b?a))a is deterministic; this is because n's right subtree is non-nullable, which prevents that Next(n, a) and Witness(n, a) both follow a same position p. It is not hard to see, and is formally shown in the proof of Theorem 3.5, that the first combination occurs if and only if the right-child of n is nullable.

Let us now consider combination (2). This combination can only occur if there is a * -node S = pStar (n) above n, and pSupLast(n) is above this node S. Let e = (a(b?a)) * and let n be the parent of the first a-position. As we can see, this expression is deterministic. This is for a similar reason as before: because the right child of n is non-nullable. If we consider e = (a(b?a?)) * then this expression is indeed non-deterministic and it holds that both FirstPos(n, a) and Witness(n, a) follow position p, where p is for instance the b-position. Thus, combination (2) requires that the right child of n is nullable, and also that FirstPos(S, a) = FirstPos(n, a). The latter guarantees that on the path from S to FirstPos(n, a) there is nothing non-nullable "to the left", and hence, that FirstPos(n, a) follows the same position p that Witness(n, a) follows.

To check determinism of e we check (P1), (P2), and then we execute for every a ∈ Σ and every node n with color a, CheckNode(n, a) of Algorithm 2; if any call returns false, then e is non-deterministic.

(i) Follow -1 e (W ) ∩ Follow -1 e (N ) = ∅ iff Rchild e(n) is nul- lable and N = Null , (ii) Follow -1 e (W ) ∩ Follow -1 e (F ) = ∅ iff F = Null , S = Null , Rchild e(n) is nullable, FirstPos(S, a) = F , and pSupLast(n) S.
Let us prove statement (i) first. If N = Null and Rchild e(n) is nullable then Lchild e(n) is not a SupLast-node. Therefore any position in Last(Lchild e(n)) belongs to Follow -1 e (W ) ∩ Follow -1 e (N ). For the only-if direction, let q be a position in Follow -1 e (W ) ∩ Follow -1 e (N ). Then in particular N = Null . Node n is a strict ancestor of q since q ∈ Follow -1 e (W ) and n = parent e (pSupFirst(W )). As q belongs to Follow -1 e (N ), pSupLast(q) is an ancestor of n. This implies that Rchild (n) is nullable according to Lemma 2.6, since Rchild (n) = pSupFirst(W ) and W follows q.

Proof of (ii): If F = Null , S = Null , Rchild e(n) is nullable, FirstPos(S, a) = F , and pSupLast(n) S, then any q in Last(Lchild (n)) is in (Follow e )(W ) ∩ (Follow * e ) -1 (F ). Conversely, let q be a position in Follow -1 e (W )∩Follow -1 e (F ). As q belongs to Follow -1 e (W ), node n is a strict ancestor of q. If Rchild e(n) e q then q ∈ (Follow * e ) -1 (F ), hence FirstPos(S, a) = F and pSupLast(n) S, and furthermore pSupLast(q) S, so that Rchild e(n) is nullable according to Lemma 2.6. Assume now that Lchild e(n) is an ancestor of q, and let x = LCA(q, F ). As an ancestor of both q and F , Lchild e(n) is an ancestor of x. Furthermore, there is no SupLast-node between q and Lchild e(n), except possibly Lchild e(n), and there is no SupFirst-node between F and Lchild e(n). Consequently, x is non-nullable because Lchild e(n) is, and, there is no * -labeled node between x and Lchild e(n). Hence q ∈ (Follow e ) -1 (F ), and, more generally, Follow -1 e (W ) ∩ (Follow e ) -1 (F ) is empty. This means that q ∈ (Follow * e ) -1 (F ). Thus S = pStar (x) is not Null , satisfies FirstPos(S, a) = F , and is an ancestor of n since there is no * -labeled nodes between x and Lchild e(n). Accordingly, pSupLast(q) S and hence Rchild e(n) is non-nullable.

Algorithm 2 Checking determinism. procedure CheckNode(n : Node, a : Σ) : Bool

1 F ← FirstPos(n, a) 2 S ← pStar (n) 3 if Rchild e(n)

Testing Numeric Occurrences

Regular expression occurring in XML Schema may contain numeric occurrence indicators. Following the definitions in [START_REF] Kilpeläinen | One-unambiguity of regular expressions with numeric occurrence indicators[END_REF], regular expressions with numeric occurrence indicators extend regular expressions with e i..j where i ∈ N, j ∈ N ∪ {∞}, and i ≤ j. The expression e i..j denotes the union of L(e e • • • e k-times ) for i ≤ k ≤ j. Also e i denotes e i..i . The definition of determinism in presence of numeric occurrence indicators must take into accounts the iterations. Informally, e is deterministic if for every word w there exists at most one position that can be reached after reading w. For instance, e = (ab) 2..2 a(b + d) is deterministic, but e = (ab) 1..2 a is not, because w = aba can lead to two alabeled positions in e . We refer the reader to [START_REF] Kilpeläinen | One-unambiguity of regular expressions with numeric occurrence indicators[END_REF] for the notion of determinism in regular expressions with numeric occurrence indicators. Note that nested iterations can interact with each other: consider the expression e5 = ((a 2..3 +b) 2 ) 2 b from [START_REF] Kilpeläinen | One-unambiguity of regular expressions with numeric occurrence indicators[END_REF]. This expression is non-deterministic because word w = a 8 b can lead to the two b-labeled positions: to the first one if we decompose it into (a 3 ) 2 a 2 b, and to the second one with decomposition ((a 2 ) 2 ) 2 b.

In order to deal with those interactions between iterations, Kilpeläinen and Tukhanen [START_REF] Kilpeläinen | One-unambiguity of regular expressions with numeric occurrence indicators[END_REF] define the flexibility of f in e, for every subexpression f of e. They explain how to annotate, in time O(|e|), every node n of e with a Boolean value indicating the flexibility of n. Essentially, flexible iterations are the only ones we have to consider when assessing determinism (in particular * expressions are flexible). The authors give a (more accurate) characterization for determinism of numeric occurrences as Theorem 5.5 in [START_REF] Kilpeläinen | One-unambiguity of regular expressions with numeric occurrence indicators[END_REF]. This characterization can be verified in linear time using a case study similar to the one above (but with flexible iterations instead of * expressions). Therefore, given a regular expression e with numeric occurrence indicators we can decide in time O(|e|) whether or not e is deterministic.

This improves upon the complexity O(σ|e|) from [START_REF] Kilpeläinen | Checking determinism of XML schema content models in optimal time[END_REF], where σ = |Σ|. Actually, in Theorem 3.3 from [START_REF] Kilpeläinen | Checking determinism of XML schema content models in optimal time[END_REF], the complexity is stated as n 2 /(log(n)), with n representing the size of the binary representation of the regular expression. But with our notations, this translates into a quadratic O(σ|e|). Kilpelaïnen obtains this complexity by a merging-based examination of First and Follow sets, similar to the approach in [START_REF] Kilpeläinen | One-unambiguity of regular expressions with numeric occurrence indicators[END_REF], but relying on a more careful analysis of the Follow sets. Interestingly, he observes after his Theorem 3.3 that it seems difficult to go below O(σn) using his approach. We believe that our skeleton-based algorithm offers a good solution to the limitations of the merging-based approach.

Alternative Determinism Test

Determinism of e can be formulated as follows:

¬(∃p, p1, p2 ∈ Pos(e). labe(p1) = labe(p2) ∧ p1 ∈ Follow e(p) ∧ p2 ∈ Follow e(p)).
A natural question arises: Is there a logic that allows to capture determinism, and at the same time, has efficient model checking that yields a procedure for checking determinism in linear time? The answer is positive: It is possible with X = reg , the language of Regular XPath expressions with data equality tests for binary trees with data values as defined in [START_REF] Bojanczyk | XPath evaluation in linear time[END_REF].

Trees with data values allow to store with every node its label, drawn form a finite set, and additionally, a data value, drawn form an infinite set. Regular XPath allows to navigate the nodes of the tree using regular expressions of simple steps (e.g., parent to the left child) and filter expressions. Filter expressions with data equality allow essentially to test whether two nodes have the same data value. In [START_REF] Bojanczyk | XPath evaluation in linear time[END_REF] Bojańczyk and Parys show that an X = reg -expression ϕ can be evaluated over a tree t in time 2 O(|ϕ|) |t|.

We wish to construct an X = reg -expression ϕ det that captures determinism and whose size is constant i.e., does not depend on the regular expression e. The main challenge is to handle position labels of e that can be drawn from an alphabet of arbitrary size. This is accomplished by: 1) storing the labels of positions of e as data values and 2) using data equality to check whether two positions have the same label. Theorem 3.6. There exists an X = reg -expression ϕ det such that for any regular expression e, ϕ det is satisfied in e if and only if e is deterministic.

Proof. We present only the construction of ϕ det . Let SupFirst and SupLast denote X = reg -expressions that are sat-isfied only in SupFirst-and SupLast-nodes, respectively. Basically, ϕP 1 checks if (P1) is violated in e and the expression ϕ for { , } ⊆ { * , } checks whether there exist two distinct positions p1 and p2 of e such that lab(p1) = lab(p2) and (Follow e ) -1 (p1) ∩ (Follow e ) -1 (p2) = ∅.

MATCHING

In this section we present a collection of algorithms matching a word w against e. First, we present an algorithm for arbitrary deterministic regular expressions that uses the constructions from Section 3 and lowest color ancestor queries to achieve expected time complexity O(|e| + |w| log log |e|). Next, we present a matching algorithm for k-occurrence regular expressions in time O(|e| + k|w|), which is linear if k is a constant. The most intricate matching algorithm that we present in this paper is the path-decomposition algorithm. It works in time O(|e| + ce|w|), where ce is the maximal depth of alternating union and concatenation operators in e. The three algorithms above perform matching by providing a transition simulation procedure: given a position p and a symbol a return the position q labeled a that follows p, or Null if no such position exists. If e = (#e )$, matching a word w against e is straightforward: begin with position #, use the transition simulation procedure iteratively on subsequent symbols of w, and finally test if the position obtained after processing the last symbol of w is followed by $.

The algorithms above allow to match multiple input words w1, . . . , wN against one regular expression e: the corresponding running times are obtained by replacing the factor |w| by |w1| + . . . + |wN |. We also present an algorithm that runs in time O(|e| + |w1| + . . . + |wN |) for star-free deterministic regular expressions e, a setting in which none of the previously mentioned algorithms guarantee linear complexity.

In the reminder of this section, we fix a deterministic regular expression e, and when talking about positions and nodes, we implicitly mean positions and nodes of e.

Lowest Colored Ancestor Algorithm

Our previous construction that tests determinism in linear time, provides an efficient procedure for transition simulation. Recall that we color the parent of any SupFirst-node n with the labels of the positions that belong to First(n). By Lemma 3.3, given a position p and a symbol a the alabeled position q that follows p is one of: Witness(n, a), FirstPos(n, a), and Next(n, a), where n is the lowest ancestor of p with color a. We use the checkIfFollow test (Theorem 2.4) to select the correct following position q among the three candidates.

Example 4.1. Consider the expression in Figure 1, position p3, and the symbol c. The lowest ancestor of p3 with color c is n3. Here, Witness(n3, c) = p5, Next(n3, c) = p1, and FirstPos(n3, c) = Null . Using checkIfFollow we find that it is p5 that follows p3. This ends the transition simulation procedure. Now, at position p5 we read the next symbol a. The lowest ancestor of p5 with color a is again n3. This time it is FirstPos(n3, a) = p2 that follows p5.

The basic ingredient of this procedure is an efficient algorithm for answering lowest colored ancestor queries. Recall from [START_REF] Muthukrishnan | Time and space efficient method-lookup for object-oriented programs[END_REF][START_REF] Farach | Optimal parallel dictionary matching and compression[END_REF], that given a tree t with colors assigned to its nodes (some nodes possibly having multiple colors), we can preprocess t in expected time O(|t| + C), where C is the total number of color assignments, so that any lowest colored ancestor query is answered in time O(log log |t|). In this way, the transition simulation is accomplished in time O(log log |e|), which gives us the following result.

Bounded Occurrence Algorithm

A regular expressions e is called k-occurrence (k-ORE for short) if each symbol a ∈ Σ occurs at most k times in e. While every regular expression is k-ORE for a sufficiently large k, Bex et al. [START_REF] Bex | Inference of concise regular expressions and DTDs[END_REF] report that the majority of regular expressions in real-life XML schemas are in fact 1-OREs. Given a position p and a symbol a, to find the following alabeled position q we only need to perform the checkIfFollow test (Theorem 2.4) on all a-labeled positions in e, which are gathered into a designated list during preprocessing of e. Thus, transition simulation is performed in time O(k). We note that an analogous technique can be used to match a word w against a nondeterministic k-ORE e: we maintain a set P of at most k positions and when reading symbol a we identify among the a-labeled positions those that follow any of the positions in P . Here, reading one symbol requires O(k 2 ) time, and thus, the matching can be done in time O(k 2 |w|) after O(|e|) preprocessing.

Path Decomposition Algorithm

Next, we describe an algorithm for matching a word w against a regular expression e in time O(|e|+ce|w|), where ce is the maximal depth of alternating union and concatenation operators in e (as mentioned at the end of the Introduction, ce is bounded by 4 in real-life DTDs [START_REF] Grijzenhout | Quality of the XML web[END_REF]).

First, we define the function hFirst (n, a) that for a node n and a symbol a returns the unique a-labeled position in First(n) and Null if it does not exist. Queries of the form hFirst (n, a) can be answered in constant time after preprocessing in time O(|e|), but since hFirst is not used in the final algorithm, we omit the implementation details.

Climbing algorithm. We first present a simple transition simulation procedure that uses hFirst , and later improve it to obtain the desired evaluation algorithm. Given a position p and a symbol a, it suffices to find an ancestor n of p such that q = hFirst (Rchild (n), a) follows p (tested with checkIfFollow ). If such ancestor does not exists, then p has no a-labeled following position. The soundness of this procedure follows from that of checkIfFollow and the completeness from Lemma 2.5. A naïve implementation seeks the ancestor in question by climbing up the parse tree starting from p, which yields O(depth(e)) time per transition simulation and overall O(|e| + depth(e) • |w|) time for matching.

Path decomposition. Our algorithm speeds up climbing the path using jumps that follow precomputed pointers. The precomputed pointers lead to nodes where we store an aggregation of the values of hFirst for several nodes skipped during the jump. The pointers are defined using the notion of path decomposition of the parse tree.

Recall that a path decomposition of a tree is a set of pairwise disjoint paths covering all nodes of the tree, and here, a path means a sequence of nodes n1, . . . , n k such that ni is the parent of ni+1. Note that a path decomposition of a tree can be specified by the set of the top-most nodes of the paths, which is how we define the path decomposition of e. A node y of e is the top-most node of a path if it is the root of e, or satisfies one of the following conditions:

(i) SupLast(y) (ii) SupFirst(y)
(iii) y is the nullable right child of its parent, or (iv) y is the right child of a +-labeled node.

For a position p we define top(p) as the top-most node of the path of the left sibling of pSupFirst(p).

Example 4.4. Consider the regular expression presented in Figure 2 together with its path decomposition. For this expression ce = 4 because there are at most 4 alternations of union and concatenation operators on any path of the expression, and in particular, it is 4 on the path from p1 to the root node. Note that top(p1) = n3 and top(p2) = n1.

We now define the function h which is similar to hFirst but defined for top-most nodes only: h(n, a) points to the a-labeled position p such that n = top(p), i.e., we assign h(top(p), lab(p)) = p for every position p. For instance, in the expression in Figure 2, h(n3, a) = p1 and h(n1, d) = p2.

There exists a subtle connection between h and hFirst . If we consider a top-most node n, then the values of h assigned to n can be viewed as an aggregation of values of hFirst of several nodes n1, . . . , n k , which are gathered from around the path (but not from the path). The decomposition of e ensures that the aggregation is collision-free, i.e., if hFirst (ni, a) = Null for some i, then hFirst (nj, a) = Null for all j = i. Formally, we state this property as follows. Proof. Let y denote the lowest node in the path of top(p) and let p0 denote some position in Last(y). We show that p follows p0. By definition of top(p), the left sibling of pSupFirst(p) is on the path between y and top(p). Therefore, pSupLast(p0) = pSupLast(y) is an ancestor of the left sibling of pSupFirst(p) because there is no SupLast-node on a path except for the top-most node of the path. Moreover, we observe that the parent of pSupFirst(p) is labeled with . Thus, by Lemma 2.2 we get p ∈ Follow (p0). Similarly, we show that p ∈ Follow (p0). Because e is deterministic, there cannot be two different positions with the same label in Follow (p0).

Lazy arrays. To store the values of h we use lazy arrays, which we describe in detail next. This interesting data structure, known in programmer's circles [START_REF] Kecher | Reset an array in constant time[END_REF][START_REF] Moret | Algorithms from P to NP[END_REF], provides the functionality of an associative array with constant time initialization, assignment, and lookup operations. The finite set of keys K needs to be known prior to initialization of the data structure. Furthermore, every key needs to be associated with a unique element from a continuous fragment of natural numbers, and here for simplicity, we assume that K = {1, . . . , N } for some N ≥ 1.

A lazy array consists of an array A that stores the values associated with the keys, a counter C of active keys having a value assigned, and additionally two arrays B and F that store the set of active keys. At initialization, C is set to 0 and uninitialized memory of length N is allocated for each of the arrays A, F , and B (an operation assumed to work in O(1) time). To assign value v to key k, we add k to the set of active keys (if k is not in that set already), and assign We found out that in practice, hash arrays offer compatible functionality with superior performance while theoretically providing only expected O(1) time for the assignment and lookup operations. As a side note, we point out that lazy arrays stand on their own merit because they allow a constant time reset operation (by simply setting C = 0), unmatched by hash arrays (but not needed by our algorithm).

A[k] = v.
Preprocessing. We construct and fill the lazy-array h in one bottom-up traversal of e. In the same traversal we also compute an additional pointer nexttop for every position and every top-most node of a path, defined as follows. We set nexttop(n) to the lowest top-most node y of a path above parent(n) that is either the root of e, or satisfies one of the following conditions:

(1) SupLast(y)

(2) SupFirst(y)

(3) there exists a non-nullable -labeled ancestor of n in the path of y.

For instance, in the expression in Figure 2, nexttop(p3) = n5, nexttop(p4) = n6, and nexttop(p5) = n4. We point out that nexttop(n) is always the top-most node of some path, and furthermore, nexttop(n) is a strict ancestor of n. x ← nexttop(x) 6 if checkIfFollow (h(x, a), p) 7 then return h(x, a) 8 y ← pSupFirst(parent(x)) 9 if y is nullable 10 then q ← h(nexttop(y), a) 11 else q ← h(Lchild (parent(y)), a) 12 if checkIfFollow (q, p) 13 then return q 14 else return Null end procedure FindNext checks in First(parent(pSupLast(p))) (Lines 8-14) to find follow positions. This task would be easy to accomplish with hFirst through hFirst (parent(pSupLast(p)), a). Since we wish to use h instead, we need to locate the node n such that h(n, a) returns the position we look for. The location of this node depends on whether or not the node y = parent(pSupLast(p)) is nullable. If y is nullable, we perform a single nexttop jump from y to reach n. Otherwise, n is the left sibling of y. Finally, we remark that if hFirst (parent(pSupLast(p)), a) is not Null , then h(n, a) returns the same node but the converse needs not be true: even if q = h(n, a) is not Null , hFirst (parent(pSupLast(p)), a) might be Null . Consequently, we verify in Line 12 that the node q indeed follows p.

Example 4.6. Consider expression in Figure 2, position p1, and symbol d. The computation of FindNext(p1, d) follows the jump sequence: p1, parent(p1), n3, n2, n1. At node n1, h(n1, d) yields position p2, and since p2 follows p1, the procedure returns p2.

Correctness. To reason about iterations of the main loop of FindNext, we introduce this notation: nexttop 0 (n) = n, and nexttop i+1 (n) = nexttop(nexttop i (n)) for i ≥ 0. Also, the jump sequence of p is the sequence nexttop 0 (p), nexttop 1 (p), . . . , nexttop K (p), where K is such that nexttop K (p) = pSupLast(p). We call K the length of the jump sequence of p. We first show that the main loop performs a sufficient number of nexttop jumps. Lemma 4.7. Let p be a position and K the length of the jump sequence of p. For every position q that follows p, either top(q) = nexttop i (p) for some 0 ≤ i ≤ K or q belongs to First(parent(pSupLast(p))).

Proof. By Lemma 2.5 top(q) is an ancestor of p or the left sibling of a non-nullable SupFirst-ancestor of p. Furthermore, if pSupFirst(q) is nullable then top(q) is the top of the path containing parent(pSupFirst(q)). From the definition of top and nexttop, the jump sequence of p visits every SupFirst-and SupLast-ancestor of p, as well as every ancestor y of p such that y is top-most node of a path and there exists some non-nullable -labeled ancestor of p on that path.

We assume that q / ∈ First(parent(pSupLast(p))), and show that in this case no other ancestor of q needs to be visited. Under that assumption, a case analysis for Lemma 2.2 shows that pSupFirst(q) is the right sibling of pSupLast(p), or satisfies pSupLast(p) parent(pSupFirst(q)) p. If pSupFirst(q) is the right sibling of pSupLast(p), then top(q) is equal to pSupLast(p) and is therefore visited by the jump sequence. Otherwise, pSupLast(p) parent(pSupFirst(q)). By Lemma 2.6, pSupFirst(q) is nullable. Consequently, its parent belongs to the path of top(q). Furthermore, the left sibling of pSupFirst(q), and therefore its parent, are nonnullable. It follows that the parent of pSupFirst(q) is a nonnullable -labeled ancestor of p that belongs to the path of top(q) which is thus visited.

We now show the correctness of FindNext. Lemma 4.8. For any position p and any symbol a, the procedure FindNext(p, a) returns q iff q ∈ Follow (p) and lab(q) = a.

Proof. The soundness of FindNext follows from the use of checkIfFollow prior to returning a position. If a position q is labeled with a and follows p, then FindNext returns q by Lemma 4.7 and because the algorithm returns q at Line 13 if q belongs to First(parent(pSupLast(p))).

Complexity. We show that the amortized running time of the transition simulation procedure in Algorihtm 3, when matching a word w against the deterministic regular expression e, is proportional to ce, the maximal depth of alternating union and concatenation operators in e. Lemma 4.9. Procedure FindNext(p, a) works in amortized time O(ce), when matching a word against a deterministic regular expression e.

Proof. We use the potential pot of the data structure defined as a function of the current position:

pot(p) = |{v p | SupFirst(v)}|.
At the phantom position #, the initial potential is set to zero. The potential is decreased by one with every other jump through nexttop and is increased by at most one each time the transition simulation procedure is executed. Now, let q be the position returned by FindNext(p, q), i.e., the a-labeled position that follows p in e. We prove that FindNext(p, a) executes at most 2(pot(q)-pot(p))+ce+O(1) iterations of the loop (nexttop jumps) before returning q.

By definition of top, there are no SupFirst-nodes between pSupFirst(q) and top(q), hence pot(q) ≤ pot(top(q)) + 1.

(

) 1
Let K be the length of the jump sequence of p and let ni = nexttop i (p) for 0 ≤ i ≤ K. Now, from the sequence n0, . . . , nK we remove every node that is the non-nullable right child of a +-labeled node and obtain a subsequence ni 0 , ni 1 , . . . , ni K . For every 0 ≤ j < K -1, if ni j is the nullable right child of its parent, then ni j+1 is a SupFirstnode by definition of nexttop. Hence, for every 0

≤ j ≤ K , j ≤ 2(pot(ni 0 ) -pot(ni j )) + 2.
Thus, for every 0

≤ j ≤ K, j ≤ 2(pot(p) -pot(nj)) + 2 + K -K . (2)
Let be the natural number such that n = top(q). Combining equations ( 1) and ( 2), as ce is an upper bound for K -K , we obtain the result claimed before:

≤ 2(pot(p) -pot(q)) + 4 + ce.

From this result, establishing the amortized complexity is straightforward. Given a word w = a1 • • • an, let p1, . . . , pn be the sequence of positions with pi = FindNext(pi-1, ai) for 1 ≤ i ≤ n and p0 = #. Then, the number of iterations through the loop of FindNext while matching w against e is at most:

n(4 + ce) + 2 n i=1
(pot(pi-1) -pot(pi))

= n(4 + ce) + 2(pot(p0) -pot(pn))

≤ n(4 + ce).

This implies the amortized cost of O(ce), because each line of FindNext runs in constant time.

Note that in the previous proof it suffices to take a smaller value of ce, the maximum number of ancestors of a position of e that are labeled with +, are non-nullable, and have a parent labeled with .

Finally, we formally state the result.

Theorem 4.10. For any deterministic regular expression e, after preprocessing in time O(|e|), we can decide for any word w whether w ∈ L(e) in time O(ce|w|), where ce is the maximal depth of alternating union and concatenation operators in e.

Star-Free Algorithm

Finally, we present an algorithm that matches simultaneously several words w1, . . . , wN against a star-free deterministic regular expression e. For a single word this is trivial: in a star-free regular expression, q ∈ Follow (p) implies that position q is after p in the preorder traversal of e, and therefore, to simulate a transition it suffices to run the checkIfFollow test on subsequent positions until a match is found. In fact, the checkIfFollow tests can be hard-coded into the traversal to avoid lowest common ancestor queries.

The result is non-trivial when matching several words w1, . . . , wN . Also this time, the expression is traversed only once and for every word wi we maintain the current index di, indicating the prefix of wi matched so far. The matching is driven by the preorder traversal of e: with every position visited in the traversal we update the indices d1, . . . , dN accordingly. The update process is, however, not straightforward and to perform it efficiently we use a variant of the a-skeleta, constructed dynamically.

First, we define some terminology. We say that the word wi at index di expects the symbol a if the symbol of wi at index di + 1 is a. We also say that wi at di reaches position p if after simulating transitions on the corresponding prefix of wi we arrive at p (or more precisely, the Glushkov automaton of e reaches p after reading the prefix of wi). A dynamic a-skeleton ta is essentially a structure containing a subset of positions closed under lowest common ancestors. Additionally, with each position p in ta we associate a list of (pointers to) words such that if word wi is associated with p, then the word wi at index di reaches the position p and expects the symbol a.

When processing a position p labeled a, we remove from the dynamic a-skeleton ta every position q that is followed by p, update indices of the words on the list associated with q, and insert p to some dynamic a-skeleta accordingly. We illustrate the procedure in the following example.

Example 4.11. We consider the deterministic regular expression e = (#(((a + ba)(c?))(d?b)))$, where # and $ are two phantom positions that do not need to be matched. The expression e has 8 positions: #, p1, . . . , p6, $. We match against e the words w1 = bcdb, w2 = acdba, w3 = acb, and w4 = bada.

Initially, all indices are d1 = d2 = d3 = d4 = 0. When describing dynamic a-skeleta, we write p, W to indicate that a position p has an associated list of words W . Initially, ta = #, [w2, w3] , t b = #, [w1, w4] , and all other dynamic a-skeleta are empty.

In the first step, we read the a-labeled position p1. Because p1 follows #, we remove from ta the position #, [w2, w3] , increment d2 and d3, and insert p1, [w2, w3] to tc.

Next, we read the b-labeled position p2. Because p2 follows #, we remove from t b the position #, [w1, w4] , increment d1 and d4, and insert p2, [w4] to ta and p2, [w1] to tc. Because we keep the dynamic a-skeleta closed under lowest common ancestors, tc becomes p1, [w2, w3] + p2, [w1] , where + is a binary node whose children are p1 and p2.

At the position p3 labeled with a, because p3 follows p2, we remove p2, [w4] from ta, increment d4 and add p3, [w4] to t d . At the position p4 labeled with c, because p4 follows p1, we remove from tc the position p1, [w2, w3] , increment d2 and d3, and insert p4, [w2] to t d and p4, [w3] to t b . Although p2 is not followed by p4, we also remove p2, [w1] from tc and discard it because we observe that p2 will not be followed by any of the subsequent positions. After this step, t b = p4, [w3] , tc is empty, and t d = p3, [w4] p4, [w2] . The next position p5 is labeled with d and follows both p3 and p4. Therefore, we remove from t d both p3, [w4] and p4, [w2] , increment d2 and d4, and insert p5, [w4] to ta and p5, [w2] to t b . This way, t b is p4, [w3] p5, [w2] . In the last step we move to the position p6 labeled with b. Because p6 follows both p4 and p5, we remove p5, [w2] and p4, [w3] from t b and increment d2 and d3. We insert p6, [w2] to ta. Because d3 = |w3| and $ follows p6, w3 matches e. Since there are no further positions to process, the words w1, w2, and w4 do not match d.

Details on how to efficiently handle a-skeleta follow. We assume that the positions p1, . . . , pm of e are given in the traversal order of e and that e has been preprocessed for LCA and Last queries. Every time we process a position p, W , the list W is nonempty and we increment the index of every word in W , which corresponds to consuming one symbol of every word in W . By |ta| we denote the number of all nodes that are inserted to ta throughout the execution of the matching algorithm. Note that for every consumed symbol we add to a-skeleta at most one position and at most one additional LCA node. Therefore, the sum of |ta| over a ∈ Σ is in O(|w1| + • • • + |wN |). We shall use this observation when characterizing the total time necessary to identify, remove, and insert positions in the dynamic a-skeleta.

With every dynamic a-skeleton ta we maintain the rightmost position pa, i.e., the position most recently added to ta. We also provide a procedure findLCA(ta, pi) for localizing in ta the possible position of the lowest common ancestor nLCA of pa and a new position pi which follows pa in the traversal of e. Note that nLCA needs not be present in ta and findLCA(ta, pi) returns the top-most descendant of nLCA present in ta (which may possibly be nLCA itself if ta contains it). The procedure simply climbs the right-most path in ta until the desired node is found. Furthermore, our algorithm performs calls to findLCA with subsequent positions in the traversal order, i.e., if a call findLCA(ta, pi) is followed by a call findLCA(ta, pj), then i < j. The procedure findLCA takes advantage of this assumption by saving the result of the previous call and beginning to climb the right-most path of ta from the saved node (if no new nodes have been added in between). This way the cumulative execution time of all findLCA calls with ta is O(|ta|), which sums over a ∈ Σ to O(|w1|

+ • • • + |wN |).
The findLCA procedure is used to insert new positions as well as to identify and to remove relevant positions from the dynamic a-skeleta. Inserting pi into ta is straightforward: we find the lowest common ancestor nLCA of na and pi in e, use findLCA(ta, pi)) to find if and where to insert nLCA to ta, and then insert pi. Identifying and retrieving positions in ta that are followed by pi is based on Lemma 2.2. We climb the path from findLCA(ta, pi) to ni = parent(pSupFirst(pi)) and at every -labeled node n we pick the subtree t rooted at the left child of n. In one traversal of t we retrieve all of its Last-positions, because they are followed by pi, and remove all remaining nodes, because none of the remaining positions is followed by any of the subsequent positions p j≥i . Again, because the number of nodes traversed by the procedure in ta is proportional to |ta|, the overall time necessary to insert and remove positions in all a-skeleta is O(|w1|

+ • • • + |wN |).

CONCLUSIONS

We have presented a linear time algorithm for testing if a regular expression is deterministic, an efficient algorithm for matching words against deterministic regular expressions, and linear time algorithms for matching against k-occurrence, * -free (multiple words), and bounded +-depth expressions.

It was our original motivation for this work, but remains an open theoretical problem, whether matching for deterministic regular expressions can be carried out in time O(|e|+ |w|). We note that our O(|e| + |w| log log |e|) matching algorithm is not optimal because of the O(log log |e|) cost of lowest color ancestor queries. We plan to find out if the cost of those lowest colored ancestor queries can be amortized and if the particular order of the queries can be used to devise better data structures. Can other approaches solve the problem in O(|e| + |w|) time, e.g., by giving up the the streaming aspect of using transition simulation? Which larger classes of regular expressions, exceeding the deterministic ones, can be matched efficiently? An example of such class is mentioned after Theorem 4.3, the k-OREs. Another interesting and largely open problem is the one of matching under linear time preprocessing of w. Very simple matching problems such as substring search have time O(|e|) solutions; can those be extended to more general regular expressions? Finally, can lower bounds matching the upper bounds be shown? Note that for general regular expressions and NFAs, it is known that no approach relying on constructing an equivalent epsilon-free NFA can achieve linear complexity. This follows from the fact that all epsilon-free NFAs equivalent to a1?a2? . . . am? have at least m log 2 m transitions [START_REF] Schnitger | Regular expressions and NFAs without epsilon-transitions[END_REF].

)

  Deterministic regular expression can be matched in time O(|e| + |w|) against an input word w, if (a) each symbol occurs only a bounded number of times in e ("k-occurrence"), or (b) the maximal depth of alternating union and concatenation operations in e is bounded.

)

  Arbitrary deterministic regular expression can be matched in time O(|e| + |w| log log |e|).

Example 2 . 1 .

 21 Let e1 = (ab + b(b?)a) * and e2 = (a * ba + bb) * . Denote by p1, . . . , p5 the positions of e1 in left-to-right order, and by q1, . . . , q5 those of e2. Then e1 = (a1b2 + b3(b4?)a5) * and Follow e 1 (p3) = {p4, p5}. Similarly, e2 = (a * 1 b2a3 + b4b5) * , and Follow e 2 (q3) = {q1, q2, q4}. Expression e1 is deterministic, while e2 is non-deterministic because labe 2 (q2) = labe 2 (q4) = b. * ?

5 [Figure 1 :

 51 Figure 1: Expression e0 = (c?((ab * )(a?c))) * (ba).

Lemma 3 . 2 .Algorithm 1 4 n

 3214 Calling BuildNext(n, a, ∅) for each a ∈ Σ and root node n of ta takes in total time O(|e|). If any call returns false then e is non-deterministic. Otherwise, the set Next(n, a) defined during the execution consists of all positions in FollowAfter e (n) labeled a, for n ∈ Nt a and a ∈ Σ. Proof. The O(|e|) time is achieved because (1) Build-Next is called at most m-times, where m is the number of nodes of all skeleta, and m ∈ O(|e|) by Lemma 3.1, and (2) each line of the algorithm runs in constant time because |Y | ≤ 2 at each call, due to Line 10. To see the correctness consider the execution along a path in ta. If at Line 7 Computing Next(n, a), if e is deterministic. procedure BuildNext(a : Σ, n : Node, Y : Set(Node)) : Bool 1 if SupLast(n) 2 then Y ← ∅ 3 if n is the left child in ta of a -node and has a right sibling n in ta and 5

( 1 )

 1 Witness(n, a) and Next(n, a) follow p, or (2) Witness(n, a) and FirstPos(n, a) follow p, or (3) FirstPos(n, a) and Next(n, a) follow p.

Theorem 3 . 5 .

 35 Determinism of a regular expression e can be decided in time O(|e|). Proof. Let S, W , N , and F denote the nodes pStar (n), Witness(n, a), Next(n, a), and FirstPos(n, a) respectively. Since (P1) and (P2) can be tested in O(|e|) time, it suffices, by Lemma 3.4, to prove the following two statements.

is nullable and 4 ( 5 (

 45 Next(n, a) = Null or FirstPos(S, a) = F and pSupLast(n) S)) 6 then return false 7 return true end procedure

D

  = (child/[not SupFirst]) * /P P = [not child] U = ([not SupLast]/parent) * F = ([lab() = ])/to-right/D ϕ = child * /[not SupLast]/from-left/[F = (U/from-left/F )] ϕ * * = child * /[lab() = * ]/ [D = (U/[SupFirst]/parent/U/[lab() = * ]/D)] ϕ * = child * /[not SupLast]/from-left/ [(to-right/[SupFirst]/D) = (parent/U/[lab() = * ]/D)] ∪ child * /[lab() = * ]/[D = (U/from-left/F )] ϕP 1 = child * /[(to-left/[not SupFirst]/D) = (to-right/[not SupFirst]/D)] ϕ det = [not (ϕP 1 or ϕ or ϕ * or ϕ * or ϕ * * )].

Theorem 4 . 2 .

 42 For any deterministic regular expression e, after preprocessing in expected time O(|e|), we can decide for any word w whether w ∈ L(e) in time O(|w| log log |e|).

Theorem 4 . 3 .

 43 For any deterministic k-ORE e, after preprocessing in time O(|e|), we can decide for any word w whether w ∈ L(e) in time O(k|w|).

Lemma 4 . 5 .

 45 For any two different positions p and p , if top(p) = top(p ), then p and p have different labels.

6 Figure 2 :

 62 Figure 2: Path decomposition.

  To lookup key k, we return A[k] if k is active and return Null otherwise. To add a key k to the set of active keys, we increment C, set F [C] = k, and set B[k] = C. In this way a key k is active if and only if 1 ≤ B[k] ≤ C and F [B[k]] = k. Note that the first condition alone is insufficient to check if a key k is active because B has been allocated with uninitialized memory.

Algorithm 3

 3 Transition simulation. FindNext in Algorithm 3 follows nexttop pointers on the path from p to the node pSupLast(p) while attempting to find a-labeled follow positions stored in h at the visited nodes. If this does not succeed, then Transition simulation. procedure FindNext(p : Position, a : Σ) : Position 1 x ← p 2 while pSupLast(p) = x 3 if checkIfFollow (h(x, a), p) 4 then return h(x, a) 5

Theorem 4 . 12 .

 412 For any star-free deterministic regular expression e and words w1, . . . , wN , we can decide which words belong to L(e) in time O(|e| + |w1| + • • • + |wN |).

Acknowledgments

We are grateful to the PODS reviewers. Their careful reading of the earlier draft and their plentiful comments allowed to largely improve the presentation of the paper. This research has been partially supported by International Initiatives INRIA Associate Teams TRANSDUCE.


MD Kirsten Slemming

; Merete

MD J Sørensen

Ph.D Hove ; Per

Dr Med Thomsen

Carsten Sci

M.D Obel

Ph.D.; Tine B Henriksen

Ph.D M ; Karen

PhD Linnet

The association between preschool behavioural problems and internalizing difficulties at age 10-12 Years

Introduction

Internalizing disorders like depression and anxiety disorders are prevalent in children as well as in adults [START_REF] Birmaher | Childhood and adolescent depression: a review of the past 10 years. Part II[END_REF], and the public health impact of the disorders is significant [START_REF] Andrews | Preventing major depression in young people[END_REF]. Treatment strategies have so far proved less efficient than desirable and the possibility of early intervention needs further exploration [START_REF]Depression in children and young people. Identification and management in primary, community and secondary care[END_REF]. However, the value of early intervention depends upon the identification of early symptoms or risk factors and the link between early and later symptoms.

The identification of early childhood indications of an increased risk of later childhood and adult psychopathology may provide a better understanding of the developmental pathway toward psychopathology [5;28]. This is essential for accurate prediction, timely intervention, and perhaps even prevention of later problems [START_REF] Ford | The relative importance of child, family, school and neighbourhood correlates of childhood psychiatric disorder[END_REF].

In very young children, diagnostic syndromes are not yet entirely agreed upon [16;16]. Some suggest that major depressive disorder occurs as a distinct and stable depressive disorder in children as young as 2-3 years of age but that DSM diagnostic criteria for major depressive disorder (MDD) should be modified for very young children [START_REF] Luby | Preschool major depressive disorder: Preliminary validation fro developmentally modified DSM-IV criteria[END_REF][START_REF] Luby | The clinical picture of depression in preschool children[END_REF][START_REF] Luby | Characteristics of depressed preschoolers with and without anhedonia: Evidence for a melancholic depressive subtype in young children[END_REF]. Others argue that, although there may be small distinctions between the two, anxiety and depressive disorders correlate to an extent that they may be treated as one internalising disorder in preadolescents [START_REF] Karevold | Predictors and pathways from infancy to symptoms of anxiety and depression in early adolescence[END_REF].

Early occurrence of anxious and depressive symptoms may be associated with later anxious and depressive symptomatology [25;39;43]. This suggests stability of internalizing symptoms due to either persisting inherent disorder, persisting adverse environmental factors, or a combination of the two.

Childhood and adolescent internalizing disorders often co-occur with externalizing disorders [4;39;49]. Externalizing comorbid behaviour is associated with greater social and academic impairment, a more chronic course of depressive symptomatology [START_REF] Angold | Comorbidity[END_REF], and a poor response to treatment of depression [14].

A recent review points out that current data on comorbidity in preschool children is limited to co-occurrence between broad categories of emotional and behavioural disorders [START_REF] Egger | Common emotional and behavioral disorders in preschool children: presentation, nosology, and epidemiology[END_REF]. The known pattern of comorbidity between depression, anxiety disorders and oppositional defiant disorder further raises the question to what extent preschool internalizing disorders are equivalent to depressive disorders in later childhood or adulthood, and furthermore how comorbid symptoms are associated with the risk of internalizing symptoms in later life [START_REF] Egger | Common emotional and behavioral disorders in preschool children: presentation, nosology, and epidemiology[END_REF].

Previous studies have found a significant association between preschool internalizing behaviour and internalizing difficulties in school-aged children [27;34;43;44] or young adults [12;25]. One recent study found a similar association between preschool and school-age internalizing difficulties in girls only [START_REF] Pihlakoski | The continuity of psychopathology from early childhood to preadolescence: a prospective cohort study of 3-12-year-old children[END_REF]. Most of the studies were relatively small [27;34;43;44]; only three measured comorbidity [34;42;43], and one study adjusted for parental psychopathology [START_REF] Mesman | Preschool developmental pathways to preadolescent internalizing and externalizing problems[END_REF]. It is therefore not clear whether these results reflect persistency of internalizing difficulties over time, comorbid externalizing behaviour, or a chance finding in small studies. One recent study demonstrated stability over 24 months during early childhood of a diagnosis of MDD in preschool children taking into account comorbid disorders [START_REF] Luby | Preschool depression. Homotypic continuity and course over 24 months[END_REF]. Follow up well into school age is desirable however. Further studies of the association between early and later internalizing difficulties are therefore needed.

Early externalizing difficulties may be an independent risk factor for future internalizing disorders [12;34;42]. This would suggest either a common precursor for the two dimensions, a transformation of one dimension into another, or increased environmental stress due to externalizing difficulties, resulting in increased risk of internalizing disorders. To our knowledge, it is not established whether hyperactive-distractible difficulties or hostileaggressive/disruptive difficulties or both play a role in this pathway. More detailed knowledge is important for more specific definition of at-risk children. Also, the transformation of one behavioural dimension into another is an interesting aspect to consider in understanding the complex pathways toward psychopathology across developmental stages, and this issue also needs to be further explored in future studies [START_REF] Egger | Common emotional and behavioral disorders in preschool children: presentation, nosology, and epidemiology[END_REF].

Our aim was to study longitudinally the association between preschool internalizing and externalizing difficulties and the risk of internalizing difficulties at 10-12 years of age, taking into account the potential effects of comorbidity and a variety of potential confounding factors. We expected to find that preschool internalizing difficulties were followed by internalizing difficulties at 10-12 years of age.

Method Participants, design and procedures

The children included in this follow-up study were born between May 1, 1991 andApril 30, 1992 in Aarhus, Denmark. When the children were 7 to 10 months of age, their parents were invited to participate in a study of their children's health (Fig. 1). All parents of children in this age group living in the municipality of Aarhus (N = 3,383) were contacted [START_REF] Skajaa | Sundhedsprofil af småbørn og småbørnsfamilier i Århus[END_REF]. The response rate in this particular study was 79% (n = 2,664). The majority of these children were also part of a well-defined prenatal cohort, the Aarhus Birth Cohort (ABC) (n = 2,432; 72%) [41;47].The ABC is based on unselected pregnant women who planned to give birth at the only obstetrics department in the municipality. They were recruited during early pregnancy and included the vast majority of the deliveries in the municipality of Aarhus. The additional participants in the children's health study (n = 951; 28%) had either moved to the municipality of Aarhus after birth of the child or were non-responders from the ABC, they were not included in the study sample.

When the children were between 3 and 4 years old, the responders of the children's health study (n = 2,664) received a parent-administered questionnaire concerning child behaviour, health, and development and psychosocial factors in the family. Child behaviour was measured with the Preschool Behaviour Questionnaire (PBQ) [START_REF] Behar | The Preschool Behaviour Questionnaire[END_REF]. The response rate was 65% (n = 1,742). These children constituted the basis of the present study.

When the children were 10-12 years of age, the participating families received a parentadministered questionnaire, Strength and Difficulties Questionnaire (SDQ) [3;3], concerning child behavioural difficulties. The response rate was 79% (n = 1,379). For the purpose of this study, only children with complete data on PBQ and SDQ (n = 1,336) were included (Fig. 1).

The final sample consisted of 681 boys and 655 girls. All responders were Danish-speaking, but further information on ethnicity was not obtained.

Figure 1 inserted here

Preschool assessment

Sixteen items of the PBQ were used to measure child behaviour at age 3.5 years (Table 1).

The PBQ was developed in 1974 by Behar and Stringfield [6;[START_REF] Behar | A Behaviour Rating Scale for the Preschool Child[END_REF] as a modification of the Children's Behavior Questionnaire by Rutter [START_REF] Rutter | A children's behaviour questionnaire for completion by teachers: preliminary findings[END_REF]. It was originally designed for use by teachers to screen for preschool psychiatric difficulties but has also been used for maternal ratings of internalizing child behaviour [START_REF] Campbell | Follow-up of hard-to-manage preschoolers: adjustment at age 9 and predictors of continuing symptoms[END_REF]. In this study the PBQ was parent-administered.

The PBQ and the Child Behaviour Check List (CBCL) have shown a medium to high correlation between maternal ratings of items related to child behaviour of interest in this study [START_REF] Campbell | Parent-referred problem three-year-olds: developmental changes in symptoms[END_REF].

Table 1 inserted here

In the present study each item was rated 0 (does not apply), 1 (sometimes applies) or 2 (frequently applies). Only the answer "frequently applies" was considered a positive response.

Children who scored within the highest 10 th percentile on each subscale were included in three not mutually exclusive behavioural groups, anxious-fearful (n = 146; 11%), hyperactivedistractible (n = 98; 7%), and hostile-aggressive (n = 170; 13%). In order to evaluate the influence of comorbidity, we defined three additional mutually exclusive subgroups of the three preschool behavioural groups: anxious-fearful symptoms without comorbidity (n = 104; 8%), hyperactive-distractible symptoms without comorbidity (n = 52; 4%), and hostileaggressive symptoms without comorbidity (n = 110; 8%).

To expand the scale measuring preschool internalizing difficulties, we defined an additional scale, an anxious-fearful-depressive scale (n = 129; 10%), using two additional questions from the PBQ concerning anxious/depressive symptoms in the children (Table 1).

School-age assessment

When the children were 10 to 12 years old, parents completed the Danish version of the Strength and Difficulties Questionnaire (SDQ) [START_REF] Obel | Spørgeskema om barnets styrker og vanskeligheder (SDQ-Dan)[END_REF]developed by Goodman [START_REF] Goodman | Psychometric properties of the strengths and difficulties questionnaire[END_REF].

SDQ is a 25-item instrument for screening of emotional and behavioural problems in children and adolescents. The instrument consists of five subscales. Because the present study addresses internalizing difficulties, only the subscales regarding emotional difficulties is of interest in the present study.

Each item was rated 0 (does not apply), 1 (sometimes applies) or 2 (frequently applies).

Based on the recommended cut-off score on the SDQ emotional scale, children were categorized as being non-emotional (score 0-3; n = 1,133; 85 %), borderline emotional (score 4; n = 89; 7%) or emotional (score 5-10; n = 114; 8%).

Previous studies show a high reliability and validity of the SDQ as a screening instrument [20;21]. Parental SDQ predicts ICD-10 and DSM-IV diagnoses reliably [START_REF] Goodman | Psychometric properties of the strengths and difficulties questionnaire[END_REF].

Potential confounding factors

Information about potential confounding factors (gender of the child, maternal education, parental cohabitation and employment, and serious parental illness) was obtained simultaneously with the preschool data collection. Information about history of parental psychiatric admission (in-or outpatient treatment) was obtained from the Danish Psychiatric Case Register when the preschool data was collected [START_REF] Munk-Jorgensen | The Danish psychiatric register as a tool in epidemiology[END_REF].

Table 2 inserted here

Attrition analyses

Mothers of children who were included in the Aarhus Birth Cohort but were non-responders at the follow-up at 8 months (The Child Health Study) or 3.5 years (The Preschool Study) have previously been reported to be younger and with shorter educations compared with responders [START_REF] Linnet | Cigarette smoking during pregnancy and hyperactive-distractible preschoolers: a follow up study[END_REF]. Compared with responders the non-responders in the school-age study (n = 364) were more likely to have mothers with lower levels of education and parents who did not live together. No preschool differences were found regarding parental employment, gender of the child, serious parental illness, and parental psychiatric hospitalization.

Data analyses

The univariate and adjusted associations between preschool categories of behaviour and school-aged emotional difficulties were evaluated in a multinomial logistic regression model and expressed as odds ratios (OR) with 95% confidence intervals (95% CI) (Table 3). Similar analyses were performed with the mutually exclusive preschool categories (without comorbidity). Previously reported risk factors for internalizing disorders (see Table 2) were considered potential confounders in the analyses and were a priori included in the multivariate logistic regression model as a number of dummy variables equal to the number of categories minus one [START_REF] Clayton | Statistical Models in Epidemiology[END_REF]. Missing information within a variable was assigned a separate category within each variable.

We also analyzed the association between internalizing difficulties in preschool and school-age after excluding children of parents with a history of psychiatric hospitalizations and without serious parental illness (Table 3).

The results were considered statistically significant at a two-sided P value of less than 0.05. Data were analyzed by using the statistical package of STATA intercooled [1].

Results

Preschool single items and school age emotional difficulties

The distribution between the PBQ behavioural items and the SDQ emotional categories is presented in Table 1.

In the anxious-fearful scale, items related to being shy, nervous and fearful or afraid were significantly associated with school-age borderline or emotional difficulties (P value <0.05).

The two items related to preschool depressive/anxious behaviour were also significantly associated with school-age emotional difficulties.

All of the single items related to hostile-aggressive and hyperactive-distractible behaviour, except impulsivity, were also significantly associated with school-age borderline or emotional difficulties.

Confounding factors

The distribution of potential confounding factors in the preschool and school-age behavioural groups is shown in Table 2. No apparent associations were found between preschool anxiousfearful behaviour and potential confounding factors. Preschool hyperactive-distractible behaviour was more often reported when the mother was less educated (basic school only), when the parents were not cohabiting, and when they were unemployed. Boys more often had preschool hostile-aggressive behaviour.

School-age emotional difficulties were more common with less maternal education, parental unemployment, serious parental illness, and when the parents were not living together. School-age borderline emotional difficulties were also more common when the parents were not cohabiting.

Children with missing information on parental employment, co-habitant status, and serious illness were similar to children with complete data with respect to gender of the child, maternal educational level, and presence of a parental psychiatric diagnosis.

Univariate and adjusted analyses

Preschool children with anxious-fearful and hostile-aggressive behavioural problems had approximately twice the risk of emotional difficulties or borderline emotional difficulties at age 10-12 compared with well-adjusted preschool children at age 3.5 years, even after adjustment for confounding (Table 3).

In the univariate analyses, hyperactive-distractible children also had twice the risk of later emotional difficulties, but after adjustment the results from the multivariate analyses became statistically insignificant (OR 1.5; 95% CI 0.8-2.3) (Table 3).

The results were unchanged in sub-analyses of the mutually exclusive preschool groups: anxious-fearful without comorbidity (borderline emotional: OR 2.1; 95% CI 1.0-4.2; P <0.05) (emotional: OR 2.1; 95% CI 1.1-4.0), hyperactive-distractible without comorbidity (borderline emotional: OR 1.4; 95% CI 0.5-4.2) (emotional: OR 1.5; CI 0.6-3.8), and hostileaggressive without comorbidity (borderline emotional: OR 2.3; 95% CI 1.1-4.5) (emotional: OR 2.4; 95% CI 1.3-4.7).

When analyses were performed restricted to children with no parental history of psychiatric hospitalizations and no serious parental illness, the associations remained essentially unchanged (Table 3).

Table 3 inserted here

Discussion

In this study we found an association between both preschool anxious-fearful and hostileaggressive behaviour and later emotional difficulties at age 10-12 years. Comorbid difficulties within each behavioural group did not explain these findings.

The apparent association between preschool externalizing hyperactive-distractible behaviour and later emotional difficulties in the univariate analyses was not statistically significant when controlled for socio-demographic factors and family characteristics.

Our findings of an association between preschool internalizing behaviour and later emotional difficulties support our study hypothesis as well as findings from other studies [12;27;34;43;44] and indicate some degree of internalizing symptom stability. This may be due to either persistent inherent disorder, difficulty of the child, or continuous stressful life circumstances or a combination of the two. In contrast with previous studies, we were able to evaluate whether comorbidity was the explanation for the associations. We also carried out more extensive adjustments for socio-demographic factors and family characteristics than most other studies have done.

We were able to categorize preschool externalizing behaviour into hostile-aggressive and hyperactive-distractible behaviour, and we found that only hostile-aggressive behaviour was significantly associated with school-age internalizing difficulties.

Our single-item analyses also indicate that particularly hostile-aggressive items related to peer-interaction difficulties (fights, bullies, etc.) are associated with school-age emotional difficulties. This has also been indicated by previous cross-sectional and small studies on bullying behaviour and internalizing difficulties in both childhood [18;48] and adolescence [START_REF] Klomek | Bullying, depression, and suicidality in adloescents[END_REF].

We believe that we have been able to present more detailed data about internalizing symptom stability, different comorbidity patterns, including lack of comorbidity, than most previous studies in this field. Our study suggests that preschool internalizing disorders can be equivalent to internalizing disorders in later childhood. Hostile-aggressive behaviour may lead to internalizing disorder due to increased environmental stress, a common precursor for the two dimensions or a longitudinal transformation of one behavioural dimension into another in later childhood. This is an additional finding of what we expected. Our findings support the view that at least some degree of hyperactive and distractible behaviour is normal in 2-3 year old children and should not be considered a risk factor for future internalizing problems.

Our results indicate the possibility of preventing later depressive and anxious psychopathology and that intervention against internalizing as well as externalizing symptoms in early childhood may be of importance. However, because most symptomatic preschool children seem to grow out of their symptoms, there is a need to investigate further, which children need early intervention. Additionally, in the present study most school-age children with internalizing symptoms did not display symptoms in the preschool study. Therefore, the effort to detect and intervene against emotional symptoms should probably be maintained throughout childhood.

Strengths and limitations

Our study has several advantages over many of the previous studies in this field. The results are based on a large study population and include detailed information about comorbidity and potential confounding factors, which are needed to address questions about nosology, comorbidity and epidemiology in preschool psychiatric disorders [START_REF] Egger | Common emotional and behavioral disorders in preschool children: presentation, nosology, and epidemiology[END_REF]. It is a longitudinal community-based study with exposure measures collected prospectively, thereby eliminating risk of differential recall. The association under study may differ between populations, and the present study is the first known Scandinavian study of its kind and one of the first studies in the Nordic countries [START_REF] Pihlakoski | The continuity of psychopathology from early childhood to preadolescence: a prospective cohort study of 3-12-year-old children[END_REF]. Health care services in the Nordic countries differ from services in many other countries by being essentially free of charge for all inhabitants. This may influence the natural course of psychiatric disorders because access to intervention is less restricted and symptom stability may therefore be less evident. Studies conducted in different countries and settings are therefore important. Some limitations must be taken into account when interpreting the results. We attempted to adjust for the potential influence of parental psychopathology on internalizing difficulties. This was done by information from the nationwide Danish Psychiatric Registry in which all psychiatric diagnoses and severity are reported. This adjustment may be incomplete because parental psychiatric in-or outpatients are crude measures of parental psychopathology as risk factors for behavioural disorders. One previous study did, however, account for this factor in a similar manner [START_REF] Mesman | Early preschool predictors of preadolescent internalizing and externalizing DSM-IV diagnoses[END_REF].

Families invited to participate in the follow-up study when the child was 3.5 years old were responders from an earlier study when the children were 7-10 months old. Similarly, only responders of the 3.5-year follow-up were invited to participate in the follow-up when the children were 10-12 years old. This recruitment procedure may potentially cause selection bias, but only if non-responding families had children with no symptoms at age 3.5 years and many symptoms at age of 10-12 years or vice versa. Such strong associations in the nonresponders seem somewhat unlikely. However, the non-responders were more likely to be families with low maternal education and single mothers. If the children of non-responders have a higher frequency of behavioural difficulties compared with responders, and in addition have fewer resources to intervene, non-responders may have an even stronger association between early and later symptoms than our results indicate. Nevertheless, the frequency of behavioural problems reported by the mother in the preschool study (22%) was similar to that reported previously [15;26].

Our study group consisted almost entirely of Caucasians and results may not apply to children of other ethnic groups.

Information on child behaviour was based on parental reports. In general, multiinformant-reports are considered most reliable in assessment of childhood difficulties [START_REF] Jensen | Scales, diagnoses, and child psychopathology: I. CBCL and DISC relationships[END_REF] and self-reports have highly contributed to our knowledge of internal states in children as young as 5 or 6 years [START_REF] Ialongo | A further look at the prognostic power of young children's reports of depressed mood and feelings[END_REF]. The possibility exists, that parental report reflects the parent'smental state or the parent-child relationship in addition to the symptoms inherent in the child. In this case the continuity measured may be the continuity of the parent'smental state or the parent-child relationship. However, the ability to express emotions on a self-report basis requires a certain level of thought-processing that preschool children do not posses, and in general parents are considered valid informers of child internalizing problems at that age unless the parent him-or herself suffers from MDD [START_REF] Nauta | A parentreport measure of children's anxiety: psychometric properties and comparison with child-report in a clinic and normal sample[END_REF].

We were able to compare child behaviour using two different instruments because the construction of the questions related to internalizing behaviour in PBQ and SDQ is very similar. However, instruments applicable for both age groups (e.g. the CBCL) may give more comparable results than the use of two different instruments, had they been available. We used the PBQ and SDQ because there was no other validated Danish short behaviour questionnaires at the time when the study and follow-up was initiated. It would have been valuable to have had more detailed information on preschool as well as school-age internalising behaviour. Such information might help further narrow down the group of children at risk of future problems. However, such instruments were not available, nor was it considered feasible to increase the length of questionnaire in this sample, which had already taken part in several research projects. More detailed instruments are becoming more available thanks to the increasing focus on very early presentation of depressive disorders [START_REF] Luby | Preschool major depressive disorder: Preliminary validation fro developmentally modified DSM-IV criteria[END_REF]. The study was purely associational thus implications regarding causal pathways cannot be drawn based on the findings.

Clinical and research implications

There is an increasing public interest in the possibility that early intervention or preventive efforts could reduce the severity or even prevent mental disorders later in life [START_REF] Harrington | Prevention and early intervention for depression in adolescence and early adult life 15[END_REF]. Our findings suggest an association between preschool internalizing behaviour, hostile-aggressive behaviour, and internalizing difficulties in later life. Thus, very early intervention may be possible, although there is a need to further narrow down the group at risk. More attention should be drawn both to preschool internalizing as well as hostile-aggressive behaviour, but our finding of an association between preschool hostile-aggressive behaviour and internalizing difficulties in later life is new and needs to be studied further.

Depressive variables

Seems to be sad and unhappy Note: Missings: cohabitants 1: 20; unemployment 2: 56; serious parental illness 3 :60.

TABLE 3

Univariate and adjusted associations between preschool PBQ behaviour and school-aged SDQ borderline emotional (n =105) and emotional difficulties (n =136) presented as odds ratio (OR) with 95% confidence intervals (CI). Multinomial logistic regression models. N= 1,336.

Preschool

  Fights with other children/hits them

7 )

 7 Note: Missings: cohabitants 1: 20; unemployment 2: 56; serious parental illness 3 :60. * P< 0.05 **Adjusted for gender of the child, maternal education, parental cohabitants, parental employment status, serious parental illness and parental psychiatric hospitalizations. ***Same adjustment as above, restricted to children of parents without a history of psychiatric hospitalizations (n =35) and children of parents with serious illness (n = 48); N =1,253.

TABLE 2

 2 The distribution of the cohort characteristics by the preschool PBQ behavioural groups and by the school age SDQ groups.

	1,331	88 (6.6)	112 (8.4)